Greatest prime dividing the n-th cubefree number: Difference between revisions
Greatest prime dividing the n-th cubefree number (view source)
Revision as of 13:35, 7 March 2024
, 3 months ago→{{header|Wren}}: Added a further version which uses a simple sieve.
m (→{{header|Free Pascal}}: corrected calculation of highest divisor) |
(→{{header|Wren}}: Added a further version which uses a simple sieve.) |
||
Line 739:
===Version 2===
This uses a simple sieve to find cubefree numbers up to a given limit which means we only now need to factorize the numbers of interest to find the greatest prime factor.
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.
<syntaxhighlight lang="wren">import "./math" for Int
import "./fmt" for Fmt
var cubeFreeSieve = Fn.new { |n|
var cubeFree = List.filled(n+1, true)
var primes = Int.primeSieve(n.cbrt.ceil)
for (p in primes) {
var p3 = p * p * p
var k = 1
while (p3 * k <= n) {
cubeFree[p3 * k] = false
k = k + 1
}
}
return cubeFree
}
var al = [1]
var count = 1
var i = 2
var lim1 = 100
var lim2 = 1000
var max = 1e9
var cubeFree = cubeFreeSieve.call(max * 1.25)
while (count < max) {
if (cubeFree[i]) {
count = count + 1
if (count <= lim1) {
var factors = Int.primeFactors(i)
al.add(factors[-1])
if (count == lim1) {
System.print("First %(lim1) terms of a[n]:")
Fmt.tprint("$3d", al, 10)
}
} else if (count == lim2) {
var factors = Int.primeFactors(i)
Fmt.print("\nThe $,r term of a[n] is $,d.", count, factors[-1])
lim2 = lim2 * 10
}
}
i = i + 1
}</syntaxhighlight>
{{out}}
<pre>
First 100 terms of a[n]:
1 2 3 2 5 3 7 3 5 11
3 13 7 5 17 3 19 5 7 11
23 5 13 7 29 5 31 11 17 7
3 37 19 13 41 7 43 11 5 23
47 7 5 17 13 53 11 19 29 59
5 61 31 7 13 11 67 17 23 7
71 73 37 5 19 11 13 79 41 83
7 17 43 29 89 5 13 23 31 47
19 97 7 11 5 101 17 103 7 53
107 109 11 37 113 19 23 29 13 59
The 1,000th term of a[n] is 109.
The 10,000th term of a[n] is 101.
The 100,000th term of a[n] is 1,693.
The 1,000,000th term of a[n] is 1,202,057.
The 10,000,000th term of a[n] is 1,202,057.
The 100,000,000th term of a[n] is 20,743.
The 1,000,000,000th term of a[n] is 215,461.
</pre>
===Version 3===
{{trans|Phix}}
{{libheader|Wren-iterate}}
<syntaxhighlight lang="wren">import "./math" for Int
import "./fmt" for Conv, Fmt
| |||