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.ht ml

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...ec t. 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