Erdös-Selfridge categorization of primes: Difference between revisions
Content added Content deleted
(→{{header|Wren}}: Doh, need more sleep!) |
|||
| Line 315: | Line 315: | ||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
Runs in about 23.5 seconds. |
|||
Second part takes a while, about 12 minutes on my machine. |
|||
If anyone's wondering why I'm not removing duplicates from the list of prime factors, the reason is that this worsens overall time (adds about 2 minutes) even if I inline the necessary code rather than call a library function. |
|||
<lang ecmascript>import "./math" for Int |
<lang ecmascript>import "./math" for Int |
||
import "./fmt" for Fmt |
import "./fmt" for Fmt |
||
| Line 323: | Line 321: | ||
var limit = (1e6.log * 1e6 * 1.2).floor // should be more than enough |
var limit = (1e6.log * 1e6 * 1.2).floor // should be more than enough |
||
var primes = Int.primeSieve(limit) |
var primes = Int.primeSieve(limit) |
||
var prevCats = {} |
|||
var cat // recursive |
var cat // recursive |
||
cat = Fn.new { |p| |
cat = Fn.new { |p| |
||
if (prevCats.containsKey(p)) return prevCats[p] |
|||
var pf = Int.primeFactors(p+1) |
var pf = Int.primeFactors(p+1) |
||
if (pf.all { |f| f == 2 || f == 3 }) return 1 |
if (pf.all { |f| f == 2 || f == 3 }) return 1 |
||
if (p > 2) { |
|||
for (i in pf.count-1..1) { |
|||
if (pf[i-1] == pf[i]) pf.removeAt(i) |
|||
} |
|||
} |
|||
for (c in 2..11) { |
for (c in 2..11) { |
||
if (pf.all { |f| cat.call(f) < c }) |
if (pf.all { |f| cat.call(f) < c }) { |
||
prevCats[p] = c |
|||
return c |
|||
} |
|||
} |
} |
||
return 12 |
return 12 |
||