"If the facts don't fit the theory, get new facts" --Albert Einstein
Matthew Brown wrote:Interesting comment on line 43 .
Can I have that in writing pleasePaul Beckett wrote: . . . Campbell is correct . . .
I think the squaring allows for that. But surely it is simpler to use the square root?can you reduce the max number you need to check for?
I think the squaring allows for that. But surely it is simpler to use the square root?
I think it runs in quadratic time.Paul Beckett wrote: . . . the time taken is relative to the performance of the machine. . . .
~/java$ java Eratosthenes
Time for sieving 0.001s Please push "enter" to continue.
Primes found:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Total of all those primes = 1060
Duration by Paul's method = 0.002s
Please push "enter" to continue.
Primes found by Paul's method:
4 7 10 12 13 16 17 19 22 24 25 27 28 31 32 34 37 38 40 42 43 45 46 47
Total of all those primes = 659
Campbell Ritchie wrote:I tried it with a boolean[] array yesterday, taking about 3 seconds to sieve from 2 to 100000000 (1e8), but it took about 1 minute to display all those numbers on screen. For 2 to 1000000000 (1e9) I suffered an OutOfMemoryError.
Campbell Ritchie wrote:Are you using false == prime? If so, what about 0, which is an exact multiple of every number, but is not a "natural" number? And what about 1, which doesn't divide by any other numbers, but is not usually considered prime?
I seemed to get a different result from yours when I printed the numbers out.
Campbell Ritchie wrote:Please post working code, which we can actually execute and understand the output of. You ought to have posted the printing method as well, so we can see a set of prime numbers
Carey Brown wrote:I'll just add my 2cents. Using a BitSet should help with memory issues and appears to be plenty fast.
Carey Brown wrote: On my machine (your milage may vary) I ran 500,000 numbers in 0.02 seconds
Carey Brown wrote:I'll just add my 2cents. Using a BitSet should help with memory issues and appears to be plenty fast. On my machine (your milage may vary) I ran 500,000 numbers in 0.02 seconds.
Mike Simmons wrote:A next step might be to eliminate all multiples of 2 or 3. My guess is that might reduce the time by about 1/6 (since the only new skips are for multiples of 3 which aren't already multiples of 2, like 9, 15, 21, 27, 33... etc). Making the code somewhat more complex to boot. Not sure it's worth it. But I thought I'd toss it out there; maybe someone can use the idea to good effect.
Consider Paul's rocket mass heater. |