basic prime numbers

This is a discussion on basic prime numbers within the C++ Programming forums, part of the General Programming Boards category; I'm willing to bet it is the faster so far and will not be beaten. Try Code: unsigned long j ...

  1. #31
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I'm willing to bet it is the faster so far and will not be beaten.
    Try
    Code:
    unsigned long j = i * i;
    instead of
    Code:
    unsigned long j = (i << 1);


    You could also treat 2 as a special case and ignore even numbers altogether (both in looping and output).
    Last edited by anon; 06-18-2007 at 08:23 AM.
    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).

  2. #32
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    > Do your four levels of brace-less control statements also contribute to the optimization, or is that just obfuscation?

    Ha ha. Just for confusion. I'm sorry. I just like to leave braces out in my personal code because I think it makes it easier to see nested loops.

    >This algorithm is called the Sieve of Erastothenes, by the way.

    Thanks. I couldn't think of the name to save my life.

    To anon:
    Code:
    unsigned long j = i * i;
    is not the same as
    Code:
    unsigned long j = (i << 1);
    Shifting by one is *maybe* an optimization to multiplying by 2. I can't prove that it is actually faster in practice. As far as ignoring even numbers, I think that somewhere I would need a loop to ignore them anyway but it's possible that if you stored the primes differently, you could avoid that loop.
    Don't quote me on that... ...seriously

  3. #33
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Look closer. I'm not multiplying by 2, I'm squaring i. If the numbers get very high, this can skip a lot of unnecessary looping, because no multiple of i less than i squared is going to be a prime. (It makes your code a bit faster.)
    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).

  4. #34
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    I would do the special case for two, and use a vector<bool> containing only the results for odd numbers which would cut the memory usage down to one-sixteenth.
    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"

  5. #35
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    Quote Originally Posted by anon View Post
    Look closer. I'm not multiplying by 2, I'm squaring i. If the numbers get very high, this can skip a lot of unnecessary looping, because no multiple of i less than i squared is going to be a prime. (It makes your code a bit faster.)
    Ah hah! Indeed it does make the algorithm faster.
    Don't quote me on that... ...seriously

  6. #36
    Registered User
    Join Date
    Nov 2005
    Posts
    673
    I think it is kind of funny. you optimize the code, but after all that you forget to free the memory.
    maybe
    Code:
    delete []primes;
    before the return statement?

  7. #37
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254
    I know it's good practice and all, but doesn't the operating system release anything you have allocated upon exit anyways?
    Programming Your Mom. http://www.dandongs.com/

  8. #38
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,471
    I know it's good practice and all, but doesn't the operating system release anything you have allocated upon exit anyways?
    Who do you trust more? Your OS or your code?
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  9. #39
    Registered User
    Join Date
    Nov 2005
    Posts
    673
    Personally I think since the OS is coded by people just the same as us there can easily be mistakes, so I would like to be sure. Maybe the OS does return it, but I think the precaution cant hurt. Also, if the OS returned memory every time, we would not have memory leaks would we?

  10. #40
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Umm ... actually, the way the system works, it's completely impossible for the OS not to return the memory.

    But only when the program ends! And if this snippet doesn't free the memory but rather relies on the OS, because "the program ends immediately afterwards anyway", then you will get a memory leak the moment you later take this snippet and make it part of a bigger program.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  11. #41
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    Quote Originally Posted by CornedBee View Post
    Umm ... actually, the way the system works, it's completely impossible for the OS not to return the memory.

    But only when the program ends! And if this snippet doesn't free the memory but rather relies on the OS, because "the program ends immediately afterwards anyway", then you will get a memory leak the moment you later take this snippet and make it part of a bigger program.
    Impossible for Window perhaps, but not impossible for every platform under the sun.

    That last part is certainly the gotcha, using code with a leak repeatedly will surely spell trouble.
    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"

Page 3 of 3 FirstFirst 123
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, 11:12 AM
  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, 10:15 AM
  5. prime numbers
    By Unregistered in forum C Programming
    Replies: 17
    Last Post: 08-20-2002, 08:57 PM

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