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?
Printable View
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?
Yes, which is pretty much the same as what you used. I call it "perfect" because it only uses primes as trial divisors.Quote:
Originally Posted by Ideswa
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.
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.
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
Yes, up to the square root of the candidate number.Quote:
Originally Posted by Ideswa
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.Quote:
Originally Posted by laserlight