# Primes with Sieve of Eratosthenes.

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 11-13-2005
opciok95
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. :cool:

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; }```
• 11-13-2005
Happy_Reaper
You can eliminate a lot of candidates much faster simply by using Fermat's little Theorem.

http://mathworld.wolfram.com/FermatsLittleTheorem.html
• 11-13-2005
opciok95
yes, but I don't wanna use another theorem,.. I wanna stay to Erant.
anyway i don't have the level
• 11-13-2005
Happy_Reaper
So you want to know if you can use other commands to make your program faster ?
• 11-13-2005
Harbinger
Then refine the search by adding "source code"
• 11-13-2005
kermit
Quote:

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. :cool:

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.

~/
• 11-13-2005
opciok95
on a AMD Athlon64 3200 works in 1 sec :)
• 11-13-2005
opciok95
Quote:

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 :D
• 11-13-2005
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.
• 11-13-2005
Harbinger
• 11-13-2005
Cactus_Hugger
Quote:

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.
• 11-13-2005
opciok95
Quote:

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.
• 11-13-2005
quzah
I could. I'm not going to though. Put some thought into it, it's not hard.

Quzah.
• 11-14-2005
opciok95
i don't have the level, could some one help me please ? if I don't do it, its for something.
Thanks anyway...
• 11-14-2005
quzah
Just loop from wherever you start, up through the square root of your number. That's where you stop counting.

Quzah.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last