Primes with Sieve of Eratosthenes.

This is a discussion on Primes with Sieve of Eratosthenes. within the C Programming forums, part of the General Programming Boards category; The program calculates the prime numbers with the Sieve of Eratosthenes. And now im asking how could I improve the ...

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    9

    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. #2
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    You can eliminate a lot of candidates much faster simply by using Fermat's little Theorem.

    http://mathworld.wolfram.com/FermatsLittleTheorem.html
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  3. #3
    Registered User
    Join Date
    Nov 2005
    Posts
    9
    yes, but I don't wanna use another theorem,.. I wanna stay to Erant.
    anyway i don't have the level

  4. #4
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    So you want to know if you can use other commands to make your program faster ?
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  5. #5
    Super Moderator Harbinger's Avatar
    Join Date
    Nov 2004
    Posts
    74
    http://www.google.co.uk/search?q=Sieve+of+Eratosthenes
    Then refine the search by adding "source code"

  6. #6
    ... kermit's Avatar
    Join Date
    Jan 2003
    Posts
    1,528
    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.
    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. #7
    Registered User
    Join Date
    Nov 2005
    Posts
    9
    on a AMD Athlon64 3200 works in 1 sec

  8. #8
    Registered User
    Join Date
    Nov 2005
    Posts
    9
    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

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  10. #10
    Super Moderator Harbinger's Avatar
    Join Date
    Nov 2004
    Posts
    74
    Clicky Clicky, do some reading

  11. #11
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    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.
    long time; /* know C? */
    Unprecedented performance: Nothing ever ran this slow before.
    Any sufficiently advanced bug is indistinguishable from a feature.
    Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
    The best way to accelerate an IBM is at 9.8 m/s/s.
    recursion (re - cur' - zhun) n. 1. (see recursion)

  12. #12
    Registered User
    Join Date
    Nov 2005
    Posts
    9
    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.

  13. #13
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I could. I'm not going to though. Put some thought into it, it's not hard.


    Quzah.
    Hope is the first step on the road to disappointment.

  14. #14
    Registered User
    Join Date
    Nov 2005
    Posts
    9
    i don't have the level, could some one help me please ? if I don't do it, its for something.
    Thanks anyway...

  15. #15
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Just loop from wherever you start, up through the square root of your number. That's where you stop counting.


    Quzah.
    Hope is the first step on the road to disappointment.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Finding primes
    By scwizzo in forum C++ Programming
    Replies: 11
    Last Post: 09-10-2008, 06:15 PM
  2. Prime Sieve Optimization
    By rt454 in forum C++ Programming
    Replies: 9
    Last Post: 05-30-2008, 09:22 PM
  3. primes program need some help
    By Mshock in forum C Programming
    Replies: 2
    Last Post: 04-17-2006, 07:21 PM
  4. primes
    By godfather in forum C++ Programming
    Replies: 3
    Last Post: 05-08-2002, 01:44 PM
  5. sieve of Erotosthenes (HELP!!!)
    By JFK in forum C Programming
    Replies: 1
    Last Post: 02-19-2002, 11:53 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21