# Thread: Primes with Sieve of Eratosthenes.

1. ## Primes with Sieve of Eratosthenes.

The program calculates the prime numbers with the Sieve of Eratosthenes. And now im asking how could I improve the program ? Any modification would be welcome!! thanks a lot.

Code:
```#include <stdio.h>
#include <stdlib.h>

#define MAX 100
#define TRUE (1 == 1)
#define FALSE (1 == 0)

int main(int argc, char *argv[]){

int p [MAX];
int i, n, candidat;
int divisible;

p[0]=2;
p[1]=3;
n=2;

candidat = p[n-1] + 2;
while (n < MAX) {
divisible = FALSE;
for (i = 0; (i < n) && !divisible; i++)
divisible = ((candidat % p[i]) == 0);

candidat += 2;
}
for (i = 0; i < MAX; i++)
printf("%6d ", p[i]);
printf("\n\n");

system("PAUSE");
return 0;
}```

2. You can eliminate a lot of candidates much faster simply by using Fermat's little Theorem.

http://mathworld.wolfram.com/FermatsLittleTheorem.html

3. yes, but I don't wanna use another theorem,.. I wanna stay to Erant.
anyway i don't have the level

4. So you want to know if you can use other commands to make your program faster ?

Then refine the search by adding "source code"

6. Originally Posted by opciok95
The program calculates the prime numbers with the Sieve of Eratosthenes. And now im asking how could I improve the program ? Any modification would be welcome!! thanks a lot.
And this program actually works on your computer?

I compiled and ran it on my machine (An AMD Athlon64 3500+) and it was right around 100% cpu for 5 minutes straight (as I write this), with no sign of any output. I think you need to go back and rethink your algorithm. A very simple version of the sieve of Eratosthenes can generate all the prime numbers up to 10000000 in just a little over a second on my machine. Here is a hint - you do not need all that expensive modulus stuff going on to figure out a prime number.

~/

7. on a AMD Athlon64 3200 works in 1 sec

8. Originally Posted by Happy_Reaper
So you want to know if you can use other commands to make your program faster ?
Yes!!. I noticed something about you can stop by getting the sqrt of the numer. help me please

9. Dividing the number by two is nearly and only searching up that high is nearly as good as using the square root of the number. You should also only print the members of your array that contain actual valid data, not just the whole thing. Of course that would actually mean initializing it before you start using it.

Quzah.

10. Clicky Clicky, do some reading

11. Originally Posted by opciok95
on a AMD Athlon64 3200 works in 1 sec
Not the source code you posted. Check the while(n < MAX) loop. It's infinite. AFAIK, n's value never changes.

Are there two AMD Athlon 64s here? Wowza. I'm running on an AMD K6-2... 450MHz.

12. Originally Posted by quzah
Dividing the number by two is nearly and only searching up that high is nearly as good as using the square root of the number. You should also only print the members of your array that contain actual valid data, not just the whole thing. Of course that would actually mean initializing it before you start using it.

Quzah.
Could you please show me the code by using the sqrt ? thx.

13. I could. I'm not going to though. Put some thought into it, it's not hard.

Quzah.

14. i don't have the level, could some one help me please ? if I don't do it, its for something.
Thanks anyway...

15. Just loop from wherever you start, up through the square root of your number. That's where you stop counting.

Quzah.