Anonymous user
Multi-base primes: Difference between revisions
→{{header|Nim}}
m (→{{header|REXX}}: upgraded REXX program to solve for five-character numbers that are prime in the most bases.) |
|||
Line 445:
4.808196 seconds (8.58 M allocations: 357.983 MiB, 0.75% gc time)
</pre>
=={{header|Nim}}==
{{trans|Go}}
Compiled via C++ with full optimizations and runtime checks deactivated, the program takes 1 second to process up to 5 character strings and 34 seconds to process up to 6 characters (i5-8250U CPU @ 1.60GHz). Curiously, compiled via C it is slower (1.1 s and 38 seconds).
<lang Nim>import math, sequtils, strutils
const
MaxDepth = 6
Max = 36^MaxDepth - 1 # Max value for MaxDepth digits in base 36.
Digits = "0123456789abcdefghijklmnopqrstuvwxyz"
# Sieve of Erathostenes.
var composite: array[1..(Max div 2), bool] # Only odd numbers.
for i in 1..composite.high:
let n = 2 * i + 1
let n2 = n * n
if n2 > Max: break
if not composite[i]:
for k in countup(n2, Max, 2 * n):
composite[k shr 1] = true
template isPrime(n: int): bool =
if n <= 1: false
elif (n and 1) == 0: n == 2
else: not composite[n shr 1]
type Context = object
indices: seq[int]
mostBases: int
maxStrings: seq[tuple[indices, bases: seq[int]]]
func initContext(depth: int): Context =
result.indices.setLen(depth)
result.mostBases = -1
proc process(ctx: var Context) =
let minBase = max(2, max(ctx.indices) + 1)
if 37 - minBase < ctx.mostBases: return
var bases: seq[int]
for b in minBase..36:
var n = 0
for i in ctx.indices:
n = n * b + i
if n.isPrime: bases.add b
var count = bases.len
if count > ctx.mostBases:
ctx.mostBases = count
ctx.maxStrings = @{ctx.indices: bases}
elif count == ctx.mostBases:
ctx.maxStrings.add (ctx.indices, bases)
proc nestedFor(ctx: var Context; length, level: int) =
if level == ctx.indices.len:
ctx.process()
else:
ctx.indices[level] = if level == 0: 1 else: 0
while ctx.indices[level] < length:
ctx.nestedFor(length, level + 1)
inc ctx.indices[level]
for depth in 1..MaxDepth:
var ctx = initContext(depth)
ctx.nestedFor(Digits.len, 0)
echo depth, " character strings which are prime in most bases: ", ctx.maxStrings[0].bases.len
for m in ctx.maxStrings:
echo m.indices.mapIt(Digits[it]).join(), " → ", m[1].join(" ")
echo()</lang>
{{out}}
<pre>1 character strings which are prime in most bases: 34
2 → 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
2 character strings which are prime in most bases: 18
21 → 3 5 6 8 9 11 14 15 18 20 21 23 26 29 30 33 35 36
3 character strings which are prime in most bases: 18
131 → 4 5 7 8 9 10 12 14 15 18 19 20 23 25 27 29 30 34
551 → 6 7 11 13 14 15 16 17 19 21 22 24 25 26 30 32 35 36
737 → 8 9 11 12 13 15 16 17 19 22 23 24 25 26 29 30 31 36
4 character strings which are prime in most bases: 19
1727 → 8 9 11 12 13 15 16 17 19 20 22 23 24 26 27 29 31 33 36
5347 → 8 9 10 11 12 13 16 18 19 22 24 25 26 30 31 32 33 34 36
5 character strings which are prime in most bases: 18
30271 → 8 10 12 13 16 17 18 20 21 23 24 25 31 32 33 34 35 36
6 character strings which are prime in most bases: 18
441431 → 5 8 9 11 12 14 16 17 19 21 22 23 26 28 30 31 32 33</pre>
=={{header|Pascal}}==
| |||