Greatest prime dividing the n-th cubefree number: Difference between revisions
Content added Content deleted
(julia example) |
(→Version 2: Added a note and changes needed to use a BitArray for the sieve.) |
||
Line 1,063: | Line 1,063: | ||
The 10 millionth term is now found in 0.85 seconds and the 1 billionth in about 94 seconds. |
The 10 millionth term is now found in 0.85 seconds and the 1 billionth in about 94 seconds. |
||
However, a lot of memory is needed for the sieve since all values in Wren (including bools) need 8 bytes of storage each. |
However, a lot of memory is needed for the sieve since all values in Wren (including bools) need 8 bytes of storage each. |
||
We could use only 1/32nd as much memory by importing the BitArray class from [[:Category:Wren-array|Wren-array]] (see program comments for changes needed). However, unfortunately this is much slower to index than a normal List of booleans and the 10 millionth term would now take just over 2 seconds to find and the 1 billionth just under 4 minutes. |
|||
<syntaxhighlight lang="wren">import "./math" for Int |
<syntaxhighlight lang="wren">import "./math" for Int |
||
//import "./array" for BitArray |
|||
import "./fmt" for Fmt |
import "./fmt" for Fmt |
||
var cubeFreeSieve = Fn.new { |n| |
var cubeFreeSieve = Fn.new { |n| |
||
var cubeFree = List.filled(n+1, true) |
var cubeFree = List.filled(n+1, true) // or BitArray.new(n+1, true) |
||
var primes = Int.primeSieve(n.cbrt.ceil) |
var primes = Int.primeSieve(n.cbrt.ceil) |
||
for (p in primes) { |
for (p in primes) { |