# prime numbers

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 08-20-2002
Unregistered
prime numbers
I need some help. I need to see if a number entered is a prime number. Here is my code:

Code:

```/* Check to see if a number is prime or not.   A number is prime if it can only be dividied by itself and 1   but by no other number.  */ #include <stdio.h> int isPrime(int number) {   int count;   for (count=1; count<number; count++)   {       if (number % count == 0 ) return 1;   }   return 0; } int main() {   int number;   printf("Please enter a number ");   if (scanf("%d", &number) != 1)   {       printf("Invalid number entered\n");       return 1;   }   if (isPrime(number))       printf("\n%d is prime\n", number);   else       printf("\n%d is not prime\n", number);   return 0; }```
I cant seem to get the right results. What am i doing wrong? Please help
thanks
• 08-20-2002
shaik786
>for (count=1; count<number; count++)
You don't need to start the loop with 1, since any number can be divided by 1 and this function would always return(1) at the first step itself. Start it with 2 instead.
• 08-20-2002
shaik786
.... had to enter my password again
• 08-20-2002
Unregistered
It sill doesnt work properly...

Does it have something to do with th if statement in the for loop?
• 08-20-2002
Unregistered
thanks but i have tried that and it still doesnt work...

When i do that it seems to return that odd numbers are all prim, which they arent. Any ideas ???
• 08-20-2002
moonwalker
dude..
the reason why it is screwing up is because

1)
for (count=1; count<number; count++)
if (number % count == 0 ) return 1;

anything is divisible by 1, so change it to count = 2; ... ...

2)
when (number % count == 0) it means number is NOT prime
... so change return 1 to return 0 and return 0 to return 1

hope this helps..

GOOD LUCK.
• 08-20-2002
moonwalker
hmm
here's the modified code..
concentrate on the bold lines...

Code:

```/* Check to see if a number is prime or not.   A number is prime if it can only be dividied by itself and 1   but by no other number.  */ #include <stdio.h> int isPrime(int number) {   int count;   for (count=2; count<number; count++)   {       if (number % count == 0 )       {         return 0;       }   }   return 1; } int main() {   int number;   printf("Please enter a number ");   if (scanf("%d", &number) != 1)   {       printf("Invalid number entered\n");       return 1;   }   if (isPrime(number) == 1)       printf("\n%d is prime\n", number);   else       printf("\n%d is not prime\n", number);   return 0; }```
you might also want to optimize your code... for example, the loop
needn't go from count = 2 to count < number...

if you have 7 ... for example, the loop can go till 7/2 (integer
division) ... which is 3 ....
if you cross 3, there won't be any factors anyways...

this will save a lot of ****work when you're checking for huuge
numbers like 100000001 ... it only needs to check till half of that
number to see if it's prime or not..
• 08-20-2002
Unregistered
Here is my changed code

Code:

```#include <stdio.h> int isPrime(int number) {   int count;   for (count=2; count<number; count++)   {       if (number % count == 0 ) return 0;       else return 1;   }   /*return 0; */ } int main() {   int number;   printf("Please enter a number ");   if (scanf("%d", &number) != 1)   {       printf("Invalid number entered\n");       return 1;   }   if (isPrime(number))       printf("\n%d is prime\n", number);   else       printf("\n%d is not prime\n", number);   return 0; }```
It still doesnt work. Did i change it properly?
• 08-20-2002
moonwalker
hmm
read my above message... see my code..

(in your latest code, you got confused where to put
return... see my code and you'll understand)
• 08-20-2002
Unregistered
Thanks for that .
I think i should get glasses.
• 08-20-2002
Shiro
Code:

```  for (count=2; count<number; count++)   {       if (number % count == 0 ) return 0;       else return 1;   }```
Note that when you enter the for-loop, the function always exits, because of the returns in the for-loop.
• 08-20-2002
ygfperson
Re: hmm
Quote:

Originally posted by moonwalker
here's the modified code..
concentrate on the bold lines...
[edited out]
you might also want to optimize your code... for example, the loop
needn't go from count = 2 to count < number...

if you have 7 ... for example, the loop can go till 7/2 (integer
division) ... which is 3 ....
if you cross 3, there won't be any factors anyways...

this will save a lot of ****work when you're checking for huuge
numbers like 100000001 ... it only needs to check till half of that
number to see if it's prime or not..

i think you can check all numbers up to the square root of the number and still be on the safe side
• 08-20-2002
moonwalker
hmm
you're right, i missed that.

any non prime number will atleast have 3 factors (including 1, it's square root, and itself).
So if a number has less than 3 factors (out of which 2 factors
are 1 and itself), it's said to be a prime.

if we cross square root of the number (int the for loop) and
still didn't get factors (other than 1 and itself), it is definitely a prime.

also, i found out that in the for loops, instead of saying

for (i = 2; i <= sqrt(number); i++)

we can first say

tempvariable = sqrt(number);

for (i = 2; i <= tempvariable; i++)

that way, it need not calculate sqrt(number) so many times
in the for loop... so it should run faster..
• 08-20-2002
*ClownPimp*
might as well add my suggestion to the pot...

after you check for two, you only need to check every odd number after that since if, say, 8 were a factor, 2 will also be a factor

if (number == 2) return 1;
if (number % 2 == 0) return 0;

for (...; ...; count += 2)
.
.
.
• 08-20-2002
kwigibo
>>any non prime number will atleast have 3 factors (including 1, it's square root, and itself).

sqrt(21) = 4.582575...

not a factor of 21. A factor has to be an integer.

[EDIT]

Code:

```int isPrime(int n) {     int c =0, s=0;     if (n == 1) { return 0; }     if (n == 2) { return 1; }     if (n % 2 == 0) { return 0; }     s = (int)sqrt( (double)n );         for (c=3; c < s; c+=2) {         if (n % c == 0) {return 0;}     }     return 1; }```
[/EDIT]
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last