Prime numbers exercise

[Ring Nebula 57]

Hello , I am new into C++ and I have a problem which I do not fully understand how to solve
. Here is the problem and my incomplete , probably wrong solution:

Write a program that asks the user to type the value of an integer N and compute the N-st prime number.








# include <iostream>
using namespace std;
int main()
{
int N = 0;
cout << "Enter integer : ";
cin >> N ;
int counter = 0 ;
int i =1;
while ( counter <=N )
{

int p = 0;
for (int a=1 ; a<=i ; a++)
{
if (i&a == 0)
{
p++;
}


}

if (p==2)
{
counter ++;



}
i++;




}
cout << i << endl;

return 0;

}


Where are the mistakes ?

Thank you

[mpark4656]

Without the proper indentation, it's tough to follow the codes.

But I've worked with finding prime numbers before so I will provide some hints.

*** Prime numbers can be found by the following method ***

- If the number is even and it is not 2, that number is not prime.

bool isPrime = true;
int number;                // This is user input

if ( number > 2 && number % 2 == 0 )
    isPrime = false;

- If the number is odd, and it is divisible by any odd numbers less than the square root of that number (Excluding 1, of course), then that number is not prime.

bool isPrime = true;
int number;                // User Input
int squareRoot = std::sqrt ( number );

if ( number > 1 && number % 2 != 0 )
    for ( int iter = 3 ; iter <= squareRoot && isPrime ; iter += 2 )
        if ( number % iter == 0 )
            isPrime = false;

Try to understand the codes I provided and see if you can incorporate them in your program.


Since your program is supposed to find nth prime number, you will have to make some changes to the above code such that number variable starts from 2 (This is the first prime number) and keeps incrementing until that nth prime is found

[mpark4656]

Since your program requirement is to find nth prime number with n being user-specified, you will need a Loop Control Variable.

Let's say that the name of that loop control variable is index.

bool isPrime = true;
int index = 0;    // Initialize the LVC to 0
int n;                // User Input
int number = 2;

/* 
This while loop will run until the value of index equals the value of n
If the value of index equals the value of n, it means the nth prime has been found
*/
while ( index < n )
{
    .
    .
    .

    if ( isPrime )    // If the tested number is prime, increment index
        index ++;

    number ++;    // Increment number (Test the next number)
}

int nthPrime = number - 1;

The While-Loop will stop once index == n

The value of ( number - 1 ) after the while-loop stops will be the nth prime number.

I hope that gave you an idea of how to go about solving the problem.



EDIT: Since we all know that prime numbers higher than 2 are all odd, we can probably speed up the process by incrementing number variable at the end of the while loop by 2 instead of 1 and initialize number to 1, not 2. I will let you test it out.

[Ring Nebula 57]

I have been using your recomandation and I have made the following code:

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int N=0;
cout << "Enter integer: " << endl;

cin >> N;
int x=0;
int i=2;
while ( x< N)

{


if (i==2)
{

x++;
}
else if (i>2 && i%2==0)
{

break;
}
else if (i>2 && i%2!=0)
{

for (int a=3 ; a<sqrt(i); a+=2)
{
if (i%a!=0)
{
x++;

}
else if (i%a==0)
{

break;
}

}
}
i++;

}

cout << "The "<< N << "'th prime number is : " << i << endl;

}

I don't fully understand what is the diffrence between this one , and one in which I would use a bool variable. Still doesn't work , but i think this is because of the initialization of a to 3 , because for i=3,5,7 the sqrt(i)<a.
What do you think is the problem.

Thank you!

[mpark4656]

The code you have is the following, correct?

#include <iostream>
#include <cmath>
using namespace std;

int main ()
{
	int N = 0;

	cout << "Enter an integer: " << endl;

	cin >> N;

	int x = 0;
	int i = 2;

	while ( x < N )
	{
		if ( i == 2 )
			x ++;
		else if ( i > 2 && i % 2 == 0 )
			break;
		else if ( i > 2 && i % 2 != 0 )
			for ( int a = 3 ; a < sqrt ( i ) ; a += 2 ) {
				if ( i % a != 0 )
					x ++;
				else if ( i % a == 0 )
					break;
			}

		i ++;
	}

	cout << "The " << N << "th prime number is: " << i << endl;	
}

The break statements will cause the program to get out of the while loop before it can calculate the nth prime.

For example, let's say we have the following
N = 100
i = 4

Because i is larger than 2 and divisible by 2, the program will execute the break statement due to the following line

else if ( i > 2 && i % 2 == 0 )
    break;

Basically, as soon as your program finds a non-prime number, the loop stops and of course, the program will never get the nth prime in i.

The reason why I included the Boolean variable is because of the for-loop. Because the for-loop tries to divide the number by all odds number less than the square root of that number, it needs some of a flag to mark the number as non-prime and exit the for-loop. You can also use break statement here to exit the for loop as soon as it's determined that the number is not prime.

When comparing a to sqrt of i, it has to be <=, not <


Also, Because you are incrementing the value of i at the very end of the while-loop, the value of i will be 1 larger than the actual correct value of i. You probably want to decrement i before you print it.


Another algorithm to find prime is called Sieve of Eratosthenes and you can find the implementation of it in the replies of this thread: http://www.cplusplus.com/forum/general/181815/

[mpark4656]

#include <iostream>
#include <cmath>
using namespace std;

int main ()
{
	int N = 0;

	cout << "Enter an integer: " << endl;

	cin >> N;

	int x = 0;
	int i = 2;

	bool isPrime;

	while ( x < N )
	{
		isPrime = true;			// Reset the boolean variable to true
        
		if ( i == 2 )			// If the number is 2, it's prime
			isPrime = true;
		else if ( i % 2 == 0 )		// If the number is even, it's not prime
		    isPrime = false;
		else				// The number is odd
			for ( int a = 3 ; a <= sqrt ( i ) && isPrime ; a += 2 )
				if ( i % a == 0 )
					isPrime = false;
		
		if ( isPrime )			// If the number is prime, increment x
			x ++;
	
		i ++;
	}

	cout << "The " << N << "th prime number is: " << i - 1 << endl;	
}

This is one way to implement the algorithm I described above. This isn't as efficient as Sieve of Erastosthenes though.

[Ring Nebula 57]

ok, I have redone it , still without boolean variable , but using at the end of the for loop break statement when the number is not prime , and I don't understand why when I use the bool variable the values for i=3,5,7 pass the test ... Isn't a=3, and sqrt(i)<3 when i = 3,5,7 ?

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int N=0;
cout << "Enter integer: " << endl;

cin >> N;
int x=0;
int i=2;
while ( x< N)

{


if (i==2)
{

x++;
}

else if (i>2 && i%2!=0)
{

for (int a=3 ; a<=sqrt(i); a+=2)
{
if (i%a!=0)
{
x++;

}
else if (i%a==0)
{

break;
}

}
}
i++;

}

cout << "The "<< N << "'th prime number is : " << i-1 << endl;

}


So it outputs the prime number on the N+3 position because it excludes 3,5,7.

[mpark4656]

I will explain how my code works in detail first.

In my example code, the number is assumed to be prime unless proven otherwise in the following conditional statements. That's why the boolean variable is reset to true at the beginning of the while loop

bool isPrime = true;  // Assume that the number is prime


if ( i == 2 )               // i is 2 and 2 is prime
    isPrime = true;      // You can simply leave this part blank with square brackets
                               // if you want to since isPrime is already set to true

else if ( i % 2 == 0 )  // i is an even number and at this point, we know that i is larger than 2
    isPrime = false;     // Any even number larger than 2 cannot be prime, so mark bool as false

else                         // At this point, i is not 2 and i is not even. i is an odd number
    for                      // so, using for-loop, we need to test and find out if i is prime
    .
    .
    .

Now, I will explain the for-loop

(1) Let's say that we have number 3, which is i = 3

for ( int a = 3 ; a <= sqrt ( i ) && isPrime ; a += 2 )

sqrt of 3 is 1.73... and 1.73 is smaller than a = 3, so the for-loop will never execute when i = 3. So for i = 3, the boolean variable will remain true. It works out since 3 is prime.

The last conditional statement,

if ( isPrime )
    x ++;

will increment the value of x

Of course, the program will implement i as well since there is no condition set for incrementing i

(2) Now, i = 4
4 is even and because of the second conditional statement,

else if ( i % 2 == 0 )

The boolean variable will be set to false.

x will not be incremented. i will be incremented

(3) Now, i = 5

for ( int a = 3 ; a <= sqrt ( i ) && isPrime ; a += 2 )

Square Root of 5 is 2.23, which is less than a = 3. The for-loop will not execute for i =5 either. And isPrime will remain true

(4) i = 6
We already know what will happen since 6 is even.

(5) i = 7

for ( int a = 3 ; a <= sqrt ( i ) && isPrime ; a += 2 )

Square Root of 7 is 2.64 and it is still smaller than a = 3, which means again, the for-loop will not execute and isPrime remains true

(6) i = 8

(7) i = 9
9 is an odd number but it's NOT prime.

for ( int a = 3 ; a <= sqrt ( i ) && isPrime ; a += 2 )

Square Root of 9 is 3. So, the for-loop will execute since 3 <= 3 is true.

if ( i % a == 0 )
    isPrime = false;

9 % 3 == 0, so isPrime is set to false. The for-loop condition requires that isPrime to be "true" as well as a <= sqrt ( i ), so the program exits the for-loop

(8) i = 10

(9) i = 11

for ( int a = 3 ; a <= sqrt ( i ) && isPrime ; a += 2 )

Square Root of 11 is 3.31 and isPrime is set to true, so the program will enter the for-loop.

if ( i % a == 0 )
    isPrime = false;

11 % 3 == 0 is FALSE, so isPrime remains true. a gets incremented to 4
4 <= sqrt ( i ) is false and the for-loop ends. Again, isPrime is still true for 11.


I hope this gives you a clear idea of how the for-loop in my example works

Now, let's take a look at yours.

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int N = 0;
    int x = 0;
    int i = 2;

    cout << "Enter integer: " << endl;
    cin >> N;

    while ( x < N )
    {
        if ( i == 2 )
            x ++;

        else if ( i > 2 && i % 2 != 0 )
        {
            for ( int a = 3 ; a <= sqrt( i ) ; a += 2 )
            {
                if ( i % a != 0 )
                    x ++;                         // Incorrect              
                else if ( i % a == 0 )
                    break;
            }
        }

        i ++;
    }

    cout << "The "<< N << "'th prime number is : " << i - 1 << endl;

}

Let's take i = 97 as example.

Square Root of 97 is 9.87

So, in the for-loop, 97 will be divided by the following a values
3, 5, 7, 9

97 % 3 != 0
97 % 5 != 0
97 % 7 != 0
97 % 9 != 0

So in your code, x gets incremented 4 times for 97. That was your mistake.



Bottom Line: With the setup I suggested, the boolean value is probably required. If you can figure out a way to set this up without the boolean, that'd be great.

Once you understand this, try learning Sieve of Erastosthenes
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[Ring Nebula 57]

Thank you , I got it .