Thread: 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;
}

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

http://www.google.co.uk/search?q=Sieve+of+Eratosthenes
Then refine the search by adding "source code"

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.

~/

on a AMD Athlon64 3200 works in 1 sec

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

Clicky Clicky, do some reading

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.

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