Greatest prime dividing the n-th cubefree number: Difference between revisions
Greatest prime dividing the n-th cubefree number (view source)
Revision as of 10:15, 9 March 2024
, 3 months ago→Version 2: Added a note and changes needed to use a BitArray for the sieve.
(julia example) |
(→Version 2: Added a note and changes needed to use a BitArray for the sieve.) |
||
Line 1,063:
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.
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
//import "./array" for BitArray
import "./fmt" for Fmt
var cubeFreeSieve = Fn.new { |n|
var cubeFree = List.filled(n+1, true) // or BitArray.new(n+1, true)
var primes = Int.primeSieve(n.cbrt.ceil)
for (p in primes) {
| |||