1. ## Prime Number Function

I am having a bit of trouble creating a function that will determine if a number is a prime number or not. I have attempted various ways to do this, and have read up on the Seive of Eratosthenes. Here is my program to find the 1001st prime number. Tell me if I have a glaring mistake.

Code:
```#include <math.h>
#include <stdlib.h>
#include <stdio.h>

bool isPrime(int);

int main()
{
int num = 3;
int counter = 1;

while (counter < 1001)
{
if(isPrime(num) == true)
{
counter++;
num++;
}
else
num++;
}

printf("%d is the 1001st prime number", num);
system("PAUSE");
return 0;
}

bool isPrime(int num)
{
int x;

if(num % 2 == 0)
return false;

for(int x = 3; x < sqrt(num) + 1; x++)
{
if(num % x == 0)
{
return false;  //when I return false, will this break from the function and just immediately return false?
break;  //I assume this can break the loop, but how do you also break the for loop if you know its false?
}
}

if(x == num - 1)  //it got through the loop without returning false so it must be true
return true;
}```
Thanks all!

2. Yes, the glaring mistake is that isPrime does not always return true if its argument is prime, and it does not always return false if its argument is not prime. For example, it will declare that 121 is prime, but 11 is a factor of 121. It will also declare that 2 is not prime, but 2 is prime.

3. Originally Posted by laserlight
Yes, the glaring mistake is that isPrime does not always return true if its argument is prime, and it does not always return false if its argument is not prime. For example, it will declare that 121 is prime, but 11 is a factor of 121. It will also declare that 2 is not prime, but 2 is prime.
Take a look at my new code, it has some comments where I ask questions in it. Do you minding answering those for me?

4. Yes the return false will return immediately.
The check at the end is incorrect. x will not get to num - 1 as it is stopped before it reaches sqrt(num) + 1

5. I forgot to post the code where I corrected that. Anyways, my answer isn't coming out correct still. Anyone know what's wrong with this code for finding the 1001st prime number?

Code:
```#include <stdlib.h>
#include <stdio.h>
#include <math.h>
bool isPrime(int);

int main()
{
int x = 3;
int counter = 0;
while(counter<1001)
{
if(isPrime(x) == true)
counter++;
x = x + 2;
}
printf("\n");
counter++; //this accounts for 2 being prime and not evaulating true in isPrime
printf("%d is the %dth prime number\n", x, counter);
system("PAUSE");
}

bool isPrime(int x)
{
int y = 2;
while(y <= sqrt(x))
{
if(x % y == 0)
{
return false;
}
else
y++;
}
return true;
}```

6. There is no such thing as "bool" in C unless you include stdbool.h. I find it is much simpler to just use ints 1 and 0 when I need something to indicate true or false.

Code:
```#include <stdlib.h>
#include <stdio.h>
#include <math.h>
int isPrime(int x);

int main()
{
int x = 3;
int counter = 1;
while(counter<1001)
{
counter+=isPrime(x);
x = x + 2;
}
x-=2;
printf("\n");
printf("%d is the %dth prime number\n", x, counter);
system("PAUSE");
}

int isPrime(int x)
{
int y = 2;
while(y <= sqrt(x))
{
if(x % y == 0)
{
return 0;
}
else
y++;
}
return 1;
}```
Try that. I haven't run it myself, but it should put you on the right track. Be careful - I think need to subtract 2 from x after the loop, I am not sure just from looking at it. I put it in above, I'll leave it to you to check.

I have attempted various ways to do this, and have read up on the Seive of Eratosthenes.
Out of curiosity, why haven't you actually used the sieve of Eratosthenes?

Given that your loops in main() are seeking to find primes in increasing order - which is also what the Sieve of Eratosthenes generally seeks to do - not using the sieve strikes me as rather ineffective.

I have attempted various ways to do this, and have read up on the Seive of Eratosthenes.
Out of curiosity, why haven't you actually used the sieve of Eratosthenes?

<< ROFL!! >>

9. Thanks KBriggs. That works perfectly

Out of curiosity, why haven't you actually used the sieve of Eratosthenes?

<< ROFL!! >>
I just was trying to make a simple program that did what it had to do, and then I will go and try to make it efficient.

11. 7927 is a prime number, so either Project Euler is mistaken, or your program missed a number, somewhere.

Did you remember to include 2 and 3 in your list of primes?

Edit: That's the problem I see. It doesn't show 2 is a prime.

I do like your program - it's straight forward and clear.

Once you get it working accurately (always a first priority), it will gain a nice speed up by assigning a value to the sqrt(x), before the while() loop. Then in the while loop test, there will be no repeating finding the sqrt() of x, with every loop.

Code:
```int rootx = sqrt(x);
while(y<rootx) {```

7927 is a prime number, so either Project Euler is mistaken, or your program missed a number, somewhere.

Did you remember to include 2 and 3 in your list of primes?

Edit: That's the problem I see. It doesn't show 2 is a prime.

I do like your program - it's straight forward and clear.

Once you get it working accurately (always a first priority), it will gain a nice speed up by assigning a value to the sqrt(x), before the while() loop. Then in the while loop test, there will be no repeating finding the sqrt() of x, with every loop.

Code:
```int rootx = sqrt(x);
while(y<rootx) {```
I didn't realize that Euler's problem was to find the 10,001st prime and not the 1,001st prime, lol. That is the 1,001st prime number. Thanks again

13. I wrote a very similer program a while back; the difference is that I take user input to give all prime numbers on an interval (so if you say 1 to 100 then it'll list all he prime's from 1 to 100).

I use a different way to "test" if it's prime or not; I set up a loop and user the modulus operator, %, to check if numbers divide into a given number...works really well. Here's the code for the program I wrote for it:

Code:
```#include<stdio.h>

/*
Programmer: Matt Lane
Date: 10/18/10

*The purpose of this program is to determine all the prime numbers between to
numbers input by the user

*For example, if one would like to find all the prime numbers between 1 and 50,
the program should outprint this:
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47

*Note: the program can only display the last 291 prime's on a given interval.
*/

int main ()
{
/*Function prototype*/
int testprime(int);

/*variable to store the return from testprime*/
int resultprime;

/*variable to store the interval to test for prime numbers*/
int a, b;

printf("This program will take an interval [a, b] where a is > b and \n");
printf("all intergers inside the open interval to be prime. \n\n");
printf("All the intergers that are prime will be outprinted at the end \n");
printf("of the program. \n\n");

printf("Please input a value for 'a' in the interval: ");
scanf("%d", &a);
printf("\n\n");
printf("Please input a value for 'b' that is > than 'a' in the interval: ");
scanf("%d", &b);

printf("The following numbers are prime on the interval [%d, %d]: \n",a,b);

while (a <= b)
{
resultprime = testprime(a);

if (resultprime == 0)
printf("\n%d", a);

a++;
}

/*Initilize hold variable*/
char holdprogram;

/*This is to stop the program so that the user can read what
is being displayed*/
fflush(stdin);
printf("\n\n\n\nThe program is completed. \n\n\n");
printf("Press enter to continue. \n\n");
scanf("%c", &holdprogram);

/*Return a value for the int main ()*/
return 0;

}

int testprime(int inputvalue)
{

/*The variable that will be the counter-control for the loop*/
int i;

/*The variable that will be used to test if a given number divides evenly
into the inputvalue*/
int testforfactor;

/*Set i = inputvalue to ensure the loop runs the proper number of
times but doesn't change the inputvalue's value*/
i = inputvalue;

/*Initilize testforfactor to 0; this is important because if the user
inputs a number < 1 the while loop will never start; so initilizing
this variable to 0 will make the program declare the input is NOT
a prime number since the lowest prime number is > 1 - which will go
through the loop*/
testforfactor = 0;

/*2 is a special prime number because the definition of a prime number
is that the prime number is only divisble by itself and 1; well, do
to the proedure used to calculate that property - 2 will be
considered not prime because it will return a "1" in the while loop
while testforfactor is still = 0*/
if (inputvalue != 2)
{ /*if 1 statement*/

/*This if statment redirects what will be output if the user
inputs a negative number*/
if (inputvalue >= 0)
{ /*if 2 statement*/

/*Inilialize the while loop; i = inputvalue...to test if
a number is prime one must check if numbers BETWEEN the
value itself and 1 (not including itself and 1) will
divide evenly into it*/
while (i > 1)
{ /*while 1 statement*/

/*As previously stated, the program must test all
values between itself and 1; so the loop needs to
lower i so that it is =/= inputvalue but still test
if the new "i" will divide evenly into inputvalue*/
i--;

/*This if statement forces the program out of the loop
once it comes back the final time; because it doesn't
decrease the value of i until AFTER the test for the
while loop occurs...meaning that when i = 2 at the end
of one loop it goes through again but will = 1 and
will ALWAYS divide evenly*/
if (i == 1)

/*So we break out of the while loop before we test
if i = 1*/
break;

/*This is the test for factors of the inputvalue; if
a certain number between inputvalue and 1 divides
evenly, then testforfactor will = 0; if no values
divide evenly then testforfactor will always be
> 0*/
testforfactor = inputvalue % i;

/*If testforfactor = 0, then the number is not prime,
so the program needs to break out of the loop at
this point if that is true*/
if (testforfactor == 0)

/*And the break statement brings it out of the
loop*/
break;

} /*while 2 statemnt*/

/*If the while loop successfully goes through then that
means that testforfactor will never = 0 - which means the
inputvalue is a prime number*/
if (testforfactor != 0)

/*Output that the inputvalue is a prime number because
it passed all the tests to qualify as such*/
inputvalue = 0;

/*If testforfactor DOES = 0, it means that the while loop
hit it's break statment and that the inputvalue is not
a prime number */

else

/*Output that the inputvalue is not a prime number
because it did not pass all the test*/
inputvalue = 1;

} /*if 2 statement*/

/*This else statement corosponds with input value being < 0 */
else

/*Output that the inputvalue was negative and, therefore,
can not be a prime number*/
inputvalue = 1;

} /*if 1 statement*/

/*This else corosponds with input vlaue being = 2; */
else

/*Output that the inputvalue was 2 and, be the definition of a
prime number, it is a prime number*/
inputvalue = 0;

return inputvalue;
}```