prime number generator

[shivaraman]

can any one give me the code for generating prime numbers using c program

[Ganon11]

http://www.thescripts.com/forum/thread552744.html

What ideas do you have? What code have you written so far? Please show us what effort you have made to solve the problem on your own, and we will be glad to help you reach the solution.

[jbrocker]

hey
Even i am trying the same programme.
so heres the code

#include<stdio.h>
main()
{
int a,i;
for(a=3; a<=100; a++)
{
for(i=2; i<a/2; i++)
{
if(a%i==0)
{
break;
}
else
continue;
}
printf("%d\t",a);
}
}


and the output i get are all the integers from 3 to 100.
so tell me where am i going wrong.

[DeMan]

Someone suggested in another thread, that you may like to create a method isPrime (or something similar) that tests whether a number is prime. [Remember a number is prime if it is not divisible by any other prime -> and we know that the largest number that could possibly divide a number is sqrt of the number]

then you loop once through the hundred and hve something like

if(isPrime(n))
{
  printf(n);
}
 

in your loop. Hopefully the thread Ganon pointed you toward has moreinformation about this.....

[Ganon11]

Hopefully the thread Ganon pointed you toward has moreinformation about this.....

Actually, it was the thread for posting guidelines - I should probably include this link to the FAQ, as it is more recent/appropriate.

[scruggsy]

Think about what makes a number prime: It is not evenly divisible by any other prime number.
Conveniently, your program is supposed to find prime numbers.
So if you store each prime number found in an array, you can use that list to compare against. When you find a number that's not divisible by any of the prime numbers on your list, add it to the array.

[DeMan]

Actually, it was the thread for posting guidelines - I should probably include this link to the FAQ, as it is more recent/appropriate.

My bad!! I knew it had been discussed before and ASSUMED without checking - i guess we lives and learns.....

[Savage]

My bad!! I knew it had been discussed before and ASSUMED without checking - i guess we lives and learns.....

Maybe I have solution:

Any number that can't be divisible with 2 and 3 is a prime number.

SO if you could make if expession like if(a%2!=0&&a%3!=0) and then put it in
array you should get a prime number generator.

[palani12kumar]

to improve the efficiency, you modify the inner for loop by

for(i=2;i<sqrt(a);i++)
{
......
......
.....
}

[Ganon11]

Maybe I have solution:

Any number that can't be divisible with 2 and 3 is a prime number.

Not true. Consider the number 35. It's not divisible by 2 (35 / 2 = 17.5) or 3 (35 / 3 = 11.667), but it is divisible by 7 (35 / 7 = 5) and 5 (35 / 5 = 7). Thus, 35 is not prime - but your test would say it is.

[ChaseCox]

A prime number is defined as a number that is only divisible evenly by itself and one. Meaning numbers like 1,2,3,5,7...41,83...ect. To save on efficiency, you can eliminate all evens, except two, and any odd number that is evenly divible by 3,5,7,9,11...ect. The resulting numbers should all be prime.

[Savage]

Not true. Consider the number 35. It's not divisible by 2 (35 / 2 = 17.5) or 3 (35 / 3 = 11.667), but it is divisible by 7 (35 / 7 = 5) and 5 (35 / 5 = 7). Thus, 35 is not prime - but your test would say it is.

That's true.But what if we add as a divider number 5 when our "a" increases beyond value of 5.Then,the code should look like:


if(a>5) if(a%2!=0&&a%3!=0&&a%5!=0) put it in array
else if(a==3) put it in array.

[ChaseCox]

That's true.But what if we add as a divider number 5 when our "a" increases beyond value of 5.Then,the code should look like:


if(a>5) if(a%2!=0&&a%3!=0&&a%5!=0) put it in array
else if(a==3) put it in array.

Right, but 5 is prime, as is 7. So my thoughts would be to create an array of only odd numbers. Then divide each individual part of the array, by the rest of the array. If the only number it is divisble by is in the same array location as the one you are currently opperating in, then that is a prime number. Do not try and use all of those if statements, it will be computationaly poor. Always try and utilize the arrays.

[sicarie]

Right, but 5 is prime, as is 7. So my thoughts would be to create an array of only odd numbers. Then divide each individual part of the array, by the rest of the array. If the only number it is divisble by is in the same array location as the one you are currently opperating in, then that is a prime number. Do not try and use all of those if statements, it will be computationaly poor. Always try and utilize the arrays.

That's a lot of work to set up, why not just use a for loop that counts up to the number, and if it divides, then drop it, if it doesn't, put it into your array.

[ChaseCox]

That's a lot of work to set up, why not just use a for loop that counts up to the number, and if it divides, then drop it, if it doesn't, put it into your array.

Design one loop to initialize your array of odd numbers
this should equal 3 lines of code

Design another loop that divides your current element, by the entire array. (You need to be sure it only returns evenly divised integers.)
this should also equal 3-4 lines of code


If any integer value in your new array is greater than 1, then your number is not prime

[Ganon11]

How about this pseudocode:

Loop X from START to END (We are testing X to see if it is prime):
   (Right now, X is prime as far as we know.)
   bool isPrime = true;
   Loop i from 2 to X (Don't include 1 or 0, because dividing by 0 gives error, and dividing by 1 always has no remainder)
      If X is evenly divisible by i
         X is not prime.
         Change isPrime to false, break from loop (no need to continue).
      Else
         Take no action (Can't be sure it will remain prime.)
   End Loop
   (Now, isPrime correctly indicates X's state).
   If X is prime
      Take appropriate action
   Else
      Take appropriate action
End Loop

[Savage]

How about this pseudocode:

Loop X from START to END (We are testing X to see if it is prime):
   (Right now, X is prime as far as we know.)
   bool isPrime = true;
   Loop i from 2 to X (Don't include 1 or 0, because dividing by 0 gives error, and dividing by 1 always has no remainder)
      If X is evenly divisible by i
         X is not prime.
         Change isPrime to false, break from loop (no need to continue).
      Else
         Take no action (Can't be sure it will remain prime.)
   End Loop
   (Now, isPrime correctly indicates X's state).
   If X is prime
      Take appropriate action
   Else
      Take appropriate action
End Loop

Yes,that is nearly giving the corect output,if we by first else statement insert the
next code:

                else{   if(x%3==0||x%5==0||x%7==0) break;
                    printf("\t%d",x);
                    delay(50);
                    isPrime=TRUE;
                    break;
                                }

,and we before first loop:

printf("3\t5\t7");

the output in range of 3-100 is corect.


Savage.

[bluesteel]

You are all wrong. The fact that a number can't be divided by two or three does not mean it is prime. 49 can't be divided by 2 nor 3 but it is not prime. If it can be divided by 2 then it is not prime. If it has square root it's not prime. The biggest number a number can divided by is not the square root.

[DeMan]

You are all wrong. The fact that a number can't be divided by two or three does not mean it is prime. 49 can't be divided by 2 nor 3 but it is not prime. If it can be divided by 2 then it is not prime. If it has square root it's not prime. The biggest number a number can divided by is not the square root.

And you have obviously read only part of the thread...

A prime number is defined as a number that is only divisible evenly by itself and one. Meaning numbers like 1,2,3,5,7...41,83...ect. To save on efficiency, you can eliminate all evens, except two, and any odd number that is evenly divible by 3,5,7,9,11...ect. The resulting numbers should all be prime

and again

A prime number is defined as a number that is only divisible evenly by itself and one. Meaning numbers like 1,2,3,5,7...41,83...ect. To save on efficiency, you can eliminate all evens, except two, and any odd number that is evenly divible by 3,5,7,9,11...ect. The resulting numbers should all be prime

also

Not true. Consider the number 35. It's not divisible by 2 (35 / 2 = 17.5) or 3 (35 / 3 = 11.667), but it is divisible by 7 (35 / 7 = 5) and 5 (35 / 5 = 7). Thus, 35 is not prime - but your test would say it is.

Only one or two people actually appeared to say what you claim about primes being any number not divisible by 2 or 3, and they were quickly corrected (see above).



While it is true that the biggest number that divides a number is NOT the smaller than the square root, if a number does have any divisors, AT LEAST one of them MUST be less than the square root, so we only have to test to the square root.
(think about 48, - 8 is larger than sqrt(48) (or approx 6.928). However, 8 * 6 = 48 and 6 is SMALLER than 6.928. Remember we are not looking for ALL factors, we are looking for ANY.....We know that there will always be the same number of factors less than the square root as greater than......so as long as we can show there are none less than, we know there couldn't be any greater than either....)

[bluesteel]

I've thinking about this and i finally made a program able to list all the combinations possible to for a number by multiplications. It works perfectly.
I am not going to post it now because i don't have the code here. If you want to ask me for it, send an email to me (<email removed>). I will send you a copy of it. Don't wait to see it here because i always forget addresses and might never enter this site again.

[bluesteel]

And you have obviously read only part of the thread...


and again


also


Only one or two people actually appeared to say what you claim about primes being any number not divisible by 2 or 3, and they were quickly corrected (see above).



While it is true that the biggest number that divides a number is NOT the smaller than the square root, if a number does have any divisors, AT LEAST one of them MUST be less than the square root, so we only have to test to the square root.
(think about 48, - 8 is larger than sqrt(48) (or approx 6.928). However, 8 * 6 = 48 and 6 is SMALLER than 6.928. Remember we are not looking for ALL factors, we are looking for ANY.....We know that there will always be the same number of factors less than the square root as greater than......so as long as we can show there are none less than, we know there couldn't be any greater than either....)

I did know all that. That is what i took into consideration to develop my program. That is the way it works

[chella]

Not true. Consider the number 35. It's not divisible by 2 (35 / 2 = 17.5) or 3 (35 / 3 = 11.667), but it is divisible by 7 (35 / 7 = 5) and 5 (35 / 5 = 7). Thus, 35 is not prime - but your test would say it is.

Hi,
Try this code. It'll generate prime numbers from 2 to 100...

the value 'a' here stores the limit i.e,upto 100 or 200.

#include<stdio.h>
int main()
{
   int a,i;
   int flag = 0;
   for(a = 2 ; a <= 100 ;a++){
      for (i = 2; i < a ;i++){
         if (a % i == 0)
            flag = 1;
      }
      if (flag == 0)
         printf("%d\n",a);
      flag =0;
   }
   return 0;
}

Please let me know if there is any issues.

Regards,
chella

[DeMan]

That code sure will.....

[dryerlint]

ok... i tried that prime number generator and it worked! however....


when i attempted to change it slightly to make it to where anyone could put in any number and recieve back all the prime numbers up to that number, it screwed up on me. here is my changes (im bored and wanted to see if i could make it more useful to someone other than myself)

#include<stdio.h>
int main()
{
 
 int target;
 
 printf("What number would you like to see all the prime numbers to?");
 scanf("%d", &target);
 
int a,i;
   int flag = 0;
   for(a = 2 ; a <= 100 ;a++){
      for (i = 2; i < a ;i++){
         if (a % i == 0)
            flag = 1;
      }
      if (flag == 0)
         printf("%d\n",a);
      flag =0;
   }
   return 0;
}
 

and these are the errors i recieved (using Vim in Unix)

primenumbergen.c: In function `main':
primenumbergen.c:12: parse error before `int'
primenumbergen.c:14: `a' undeclared (first use in this function)
primenumbergen.c:14: (Each undeclared identifier is reported only once
primenumbergen.c:14: for each function it appears in.)
primenumbergen.c:15: `i' undeclared (first use in this function)
primenumbergen.c:17: `flag' undeclared (first use in this function)

[chella]

ok... i tried that prime number generator and it worked! however....


when i attempted to change it slightly to make it to where anyone could put in any number and recieve back all the prime numbers up to that number, it screwed up on me. here is my changes (im bored and wanted to see if i could make it more useful to someone other than myself)

#include<stdio.h>
int main()
{
 
 int target;
 
 printf("What number would you like to see all the prime numbers to?");
 scanf("%d", &target);
 
int a,i;
   int flag = 0;
   for(a = 2 ; a <= 100 ;a++){
      for (i = 2; i < a ;i++){
         if (a % i == 0)
            flag = 1;
      }
      if (flag == 0)
         printf("%d\n",a);
      flag =0;
   }
   return 0;
}
 

and these are the errors i recieved (using Vim in Unix)

primenumbergen.c: In function `main':
primenumbergen.c:12: parse error before `int'
primenumbergen.c:14: `a' undeclared (first use in this function)
primenumbergen.c:14: (Each undeclared identifier is reported only once
primenumbergen.c:14: for each function it appears in.)
primenumbergen.c:15: `i' undeclared (first use in this function)
primenumbergen.c:17: `flag' undeclared (first use in this function)

Hi,
Declare the int a, i ... before the printf & scanf stmt's.
Hope this will work :-)