Printable View
I wrote this program to help me find all the prime numbers from 2 to i. The results are good, but I feel that something goes wrong in the program. Could you help me? Is everything OK with that piece of code:
Code:#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int i, j, k, n;
printf("Give me the top number: \n");
scanf("%d", &i);
for (j=2;j<i;j++){
for (k=2;k<i;k++)
{
n=j%k;
if (n==0) break;
}if (j==k) printf("%d:%d \n",j,k);}
system("PAUSE");
return 0;
}
You can eliminate half of your checks by incrementing by 2 each time, because even numbers aren't prime. Start at 3 instead, increment by 2. Also, search the forum for prime numbers, I'm sure you'll find tons of posts.
Quzah.
* Start from 2. Test only odd numbers after that.
* You should store all existing prime numbers and use them for following computations, instead of testing each number everytime.
* Use the fact that if for all prime numbers p < sqrt(n), if none divide into n, then n is prime. Testing up to sqrt(n) is far quicker than testing up to n.
Don't believe me, believe the numbers.
:DCode:Clock cycles required to calculate primes up to n
n Yours Mine
10000 156 16
100000 16031 (15 seconds!) 109
1000000 lazy to run 2578
I'd rather believe the code, instead of numbers you pull out of your ass.
Quzah.