1. ## Just a feeling...

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;
}```

2. 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.

3. * 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.
Code:
```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```

4. I'd rather believe the code, instead of numbers you pull out of your ass.

Quzah.