Thread: basic prime numbers

  1. #1
    Registered User
    Join Date
    May 2007
    Posts
    21

    basic prime numbers

    I decided to make a small program that found prime numbers, and after an hour or so of tweaking i came up with something that was about 30 times faster than my first attempt, however I still have a couple of questions:

    1. Is there an alternative to goto
    2. How else can I optomise it further/any further improvements?
    3. It only really needs to test if it is divisible by prime numbers, not every number, is there a way of doing this without taking up too much memory, and if so what shall i use, and will it even be quicker?

    Thanks for any help:

    Code:

    Code:
    #include <iostream>
    using namespace std;
    
    // varaiables
    int num=0;
    int i;
    int j;
    int main()
    {
        for (j=1; j <=9999; ++++j)
        {
            for (i=3; i <((j+1)/2); ++++i)
            {
               if (j%i==0) goto moo;
            } 
            cout << j <<endl;
            moo:;               
        }
        cin >> num;
    }

  2. #2
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    I was always told not to use goto. You could use 'break', to get out of the loop, then only print the output if i == (j-1)/2.

    You could use bit shifting to divide by two, for some processors that works faster, but I think thats just old ones. IE: j>>1 is the same as j/2
    Last edited by mike_g; 06-16-2007 at 08:06 AM.

  3. #3
    Registered User
    Join Date
    May 2007
    Posts
    21
    i tried that option, but wouldnt that mean an extra if command which would probably slow it down?

  4. #4
    Sanity is for the weak! beene's Avatar
    Join Date
    Jul 2006
    Posts
    321
    It's a relatively small program, i don't think an extra if statement will make any difference.
    Last edited by beene; 06-16-2007 at 08:42 AM.

  5. #5
    Registered User
    Join Date
    May 2007
    Posts
    21
    Therefore double the amount of commands, pointless or not thats exactly what im trying to do; make it as fast as possible.

  6. #6
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    If you want to increase performace - store all found prime numbers and check the division only to these numbers

    And of course - the internal loop should go only upto sqrt(j)
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  7. #7
    Registered User
    Join Date
    May 2007
    Posts
    21
    ok i added that and it has sped it up to a stupid speed xD

    Code:
    #include <iostream>
    #include <math.h>
    using namespace std;
    
    // varaiables
    int num=0;
    int i;
    int j;
    double k;
    int main()
    {
        for (j=1; j <=50000000; ++++j)
        {
            k=sqrt(j);
            for (i=3; i <=k; ++++i)
            {
               if (j&#37;i==0) goto moo;
            } 
            cout << j <<endl;
            moo:;               
        }
        cin >> num;
    }

  8. #8
    The larch
    Join Date
    May 2006
    Posts
    3,573
    1) In C++ headers inherited from C are named "c+name" and without ".h". Hence: <cmath>

    2) Your varaiables shouldn't be global. Actually you should declare them at the point where you can initialize them at the same time.

    3) I'm afraid using the increment operator twice like you do may not give the same result with all compilers. If you want to increment by 2, use
    Code:
    i += 2;
    4) Your goto is fine by me if you think this speeds things up. You can make the program faster if you store the primes you have found somewhere and only do trial division with the primes you have found so far (up to the square root).

    Code:
    #include <iostream>
    #include <cmath> 
    using namespace std;
    
    int main()
    {
        for (int j=1; j <=50000000; j += 2)
        {
            double k=sqrt(j);
            for (int i=3; i <=k; i += 2)
            {
               if (j%i==0) goto moo;
            } 
            cout << j <<endl;
            moo:;               
        }
        cin >> num;
    }
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I would make all variables unsigned ints here. Certainly k being a double is going to probably mean a real->int conversion every time through the i loop.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    I'd write the inner loop and surrounding code like this, but that's just me:
    Code:
    unsigned long k = (unsigned long)(sqrt(j) + .5);
    unsigned long i;
    
    for(i = 3; j &#37; i && i <= k; i += 2);
    
    if(i <= k) cout << j << endl;
    because I think j%i has a greater chance of being true, since the majority of numbers are non primes. Just a thought.

    [edit] > I'd make all variables unsigned ints here
    Or better yet, unsigned longs, since 50 million can't nessesarily be stored in an int. [/edit]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  11. #11
    Registered User
    Join Date
    Jun 2007
    Posts
    4
    Quote Originally Posted by cakey View Post
    1. Is there an alternative to goto
    There are algorithms, that can be implemented with 'goto' - and only with 'goto'!

    'goto' is a basic jmp command your machine actually is able to understand (literally!).
    This is why goto is executed more quickly than most loops, which usually consist of a combination of many machine commands.
    So - although you are often told to avoid 'goto' and to use loops instead, 'goto' is the more optimized version in most cases.
    But nevertheless it is a good idea to use loops instead of 'goto'.
    Ha ha.

  12. #12
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> There are algorithms, that can be implemented with 'goto' - and only with 'goto'!
    Like what?

    If you're learning C++, then you should be learning about making clear, robust code first and foremost. In most cases the goto will will have no noticable positive impact on execution speed, and in most cases it will have a noticable negative impact on coding speed. That's why beginners are taught to avoid it.

  13. #13
    Registered User
    Join Date
    Jun 2007
    Posts
    4
    Quote Originally Posted by Daved View Post
    >> There are algorithms, that can be implemented with 'goto' - and only with 'goto'!
    Like what?

    If you're learning C++, then you should be learning about making clear, robust code first and foremost. In most cases the goto will will have no noticable positive impact on execution speed, and in most cases it will have a noticable negative impact on coding speed. That's why beginners are taught to avoid it.
    (Of course) (one) (should use) (loops) instead!
    Only wanted to show the positive effects of 'goto'. Most tutorials/books say it's the worst thing on earth to use 'goto' in C++ - programs. GOTO is by far not a useless basic command. There is a good reason, why almost every programming language knows the GOTO command. A language without GOTO is NOT TURING COMPLETE. Never.
    Ha ha.

  14. #14
    Registered User
    Join Date
    May 2007
    Posts
    58
    Hint. Don't look for prime numbers, look for NOT-prime numbers.

    it's like this

    Code:
    int i,j;
    
    for(i=2;i<=MAX/2;++i)
    {
        for(j=2;j<=MAX/2;++j)
        {
            if(i*j>MAX) break;
            primes[i*j]=false;
        }
    }
    Thinking like a physicist (please forgive) all numbers are prime until proved against.

    I know this method as "Striking the table", if you multiply two numbers greater than 1, you'll definitely get a non-prime number.

    On the computing side: This method is incredibly fast. I used it on an 3Ghz intel (That actually runs slower ) to compute the prime numbers from 1 to 100 millions and took 3 minutes.

    From 1 to 20.000, it's about two miliseconds of work.

    Good Luck

    PS:

    This line:
    Code:
            if(i*j>MAX) break;
    It's very important. It makes it about a hundred times faster.

  15. #15
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    because I think j&#37;i has a greater chance of being true, since the majority of numbers are non primes. Just a thought.
    Here I can think about 3 solutions

    j % i && i <= k - because first condition has bigger chance to be false

    i <= k && j % i - because the second condition check takes a lot more time than the first

    (j % i != 0) & (i <= k) - because we have only one branching - so the branch misses chance is lower

    And I'll go for one of them only after profiling...

    otherwise - I'll use the code that is easier to read - with "if" inside "for"

    Code:
    for(i = 3; i <= k; i += 2)
       if(j % i) break;
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Finding Prime Numbers
    By dan724 in forum C Programming
    Replies: 11
    Last Post: 12-14-2008, 12:12 PM
  2. prime number program with function
    By mackieinva in forum C Programming
    Replies: 17
    Last Post: 09-20-2007, 08:36 AM
  3. prime numbers code compile error
    By Tony654321 in forum C Programming
    Replies: 5
    Last Post: 10-10-2004, 10:13 AM
  4. the definition of a mathematical "average" or "mean"
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 12-03-2002, 11:15 AM
  5. prime numbers
    By Unregistered in forum C Programming
    Replies: 17
    Last Post: 08-20-2002, 08:57 PM