help, trying to find prime number

This is a discussion on help, trying to find prime number within the C++ Programming forums, part of the General Programming Boards category; Yeah, I printf() them. Without printing it's 1.8 secs. I have looked into wikipedia on Trial division - Wikipedia, the ...

  1. #16
    C / C++
    Join Date
    Jan 2006
    Location
    The Netherlands
    Posts
    312
    Yeah, I printf() them. Without printing it's 1.8 secs. I have looked into wikipedia on Trial division - Wikipedia, the free encyclopedia, is that the algorithm you use? That is just the "brute force" one right? Then what is perfect to it?
    Last edited by Ideswa; 05-02-2009 at 06:47 AM.
    Operating Systems:
    - Ubuntu 9.04
    - XP

    Compiler: gcc

  2. #17
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,113
    Quote Originally Posted by Ideswa
    I have looked into wikipedia on Trial division - Wikipedia, the free encyclopedia, is that the algorithm you use?
    Yes, which is pretty much the same as what you used. I call it "perfect" because it only uses primes as trial divisors.

    The sieve of Eratosthenes is likely to be much faster and yet feasible in this case of just finding the primes less than one million.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #18
    C / C++
    Join Date
    Jan 2006
    Location
    The Netherlands
    Posts
    312
    The sieve is memory-heavy though?
    So you store primes in an array or something and when you check integer 'n' for primality you check if 'n mod x' != 0 where x are only primes you calculated before?

    Edit: I now store validated primes in an array and only use the modulus with the primes in that array. Time without printf() now is 0.7 secs for integers up to 1 million.
    Last edited by Ideswa; 05-02-2009 at 07:00 AM.
    Operating Systems:
    - Ubuntu 9.04
    - XP

    Compiler: gcc

  4. #19
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,113
    Quote Originally Posted by Ideswa
    The sieve is memory-heavy though?
    Assuming CHAR_BIT is 8, you could store a million bits in 125000 bytes. But even if you use ints instead (bools would be most natural option), that would still be less than sizeof(int) megabytes of memory needed, which should fit on the stack too.

    Quote Originally Posted by Ideswa
    So you store primes in an array or something and when you check integer 'n' for primality you check if 'n mod x' != 0 where x are only primes you calculated before?
    Yes, up to the square root of the candidate number.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #20
    Registered User
    Join Date
    May 2009
    Posts
    16
    Quote Originally Posted by laserlight View Post
    hmm... there might be another reason: did you print out all the primes found? When I changed my implementation to do that (since that is what vampirekid.13 did, after all), the time taken was in the neighbourhood of 2.25 seconds.
    u guys are a lot more advanced than me however, i just made a quick program because it was a project for my c++ tutorial, i appreciate the great advice and as i get further and learn more ill make it better, but as of right now i dont really know how to "break" out of a loop, i know how to skip the prime numbers tho so i guess i can add that in. but yea, you guys prolly did this for years now, im on my first week.

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

Similar Threads

  1. prime number program with function
    By mackieinva in forum C Programming
    Replies: 17
    Last Post: 09-20-2007, 09:36 AM
  2. for loop to find prime numbers
    By 1rwhites in forum C Programming
    Replies: 11
    Last Post: 10-21-2005, 11:37 AM
  3. Prime Number stops after 29, but why?
    By Daveo in forum C Programming
    Replies: 22
    Last Post: 09-17-2004, 11:55 AM
  4. prime # query
    By alokin in forum C Programming
    Replies: 8
    Last Post: 09-04-2002, 12:50 PM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 05:56 PM

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