Anaprimes: Difference between revisions

2,954 bytes added ,  1 year ago
Created Nim solution.
(→‎{{header|jq}}: def primeSieve:)
(Created Nim solution.)
Line 522:
For 10-digit primes, a largest anagram group, [1123465789, ..9876543211], has a group size of 152526.
186.920326 seconds (455.94 M allocations: 72.961 GiB, 1.54% gc time, 0.02% compilation time)
</pre>
 
=={{header|Nim}}==
{{trans|Wren}}
Run in 14 seconds on an Intel Core i5-8250U (four cores at 1.60GHz).
<syntaxhighlight lang="Nim">import std/[algorithm, bitops, math, strformat, strutils, tables]
 
type Sieve = object
data: seq[byte]
 
func `[]`(sieve: Sieve; idx: Positive): bool =
## Return value of element at index "idx".
let idx = idx shr 1
let iByte = idx shr 3
let iBit = idx and 7
result = sieve.data[iByte].testBit(iBit)
 
func `[]=`(sieve: var Sieve; idx: Positive; val: bool) =
## Set value of element at index "idx".
let idx = idx shr 1
let iByte = idx shr 3
let iBit = idx and 7
if val: sieve.data[iByte].setBit(iBit)
else: sieve.data[iByte].clearBit(iBit)
 
func newSieve(lim: Positive): Sieve =
## Create a sieve with given maximal index.
result.data = newSeq[byte]((lim + 16) shr 4)
 
func initPrimes(lim: Positive): seq[Natural] =
## Initialize the list of primes from 2 to "lim".
var composite = newSieve(lim)
composite[1] = true
for n in countup(3, sqrt(lim.toFloat).int, 2):
if not composite[n]:
for k in countup(n * n, lim, 2 * n):
composite[k] = true
result.add 2
for n in countup(3, lim, 2):
if not composite[n]:
result.add n
 
proc digits(n: Positive): seq[0..9] =
var n = n.Natural
while n != 0:
result.add n mod 10
n = n div 10
 
const Limit = 1_000_000_000
const MaxIndex = log10(Limit.toFloat).int
let primes = initPrimes(Limit)
 
var anaPrimes: Table[int, seq[int]]
for p in primes:
var key = 1
for digit in p.digits:
key *= primes[digit]
anaPrimes.mgetOrPut(key, @[]).add p
 
var largest: array[1..MaxIndex, int]
var groups: array[1..MaxIndex, seq[seq[int]]]
for key, values in anaPrimes.pairs:
let nd = values[0].digits.len
if values.len > largest[nd]:
largest[nd] = values.len
groups[nd] = @[values]
elif values.len == largest[nd]:
groups[nd].add values
 
var j = 1000
for i in 3..MaxIndex:
echo &"Largest group(s) of anaprimes before {insertSep($j)}: {largest[i]} members:"
groups[i].sort(proc (x, y: seq[int]): int = cmp(x[0], y[0]))
for g in groups[i]:
echo &" First: {insertSep($g[0])} Last: {insertSep($g[^1])}"
j *= 10
echo()
</syntaxhighlight>
 
{{out}}
<pre>Largest group(s) of anaprimes before 1_000: 4 members:
First: 149 Last: 941
First: 179 Last: 971
First: 379 Last: 937
 
Largest group(s) of anaprimes before 10_000: 11 members:
First: 1_237 Last: 7_321
First: 1_279 Last: 9_721
 
Largest group(s) of anaprimes before 100_000: 39 members:
First: 13_789 Last: 98_731
 
Largest group(s) of anaprimes before 1_000_000: 148 members:
First: 123_479 Last: 974_213
 
Largest group(s) of anaprimes before 10_000_000: 731 members:
First: 1_235_789 Last: 9_875_321
 
Largest group(s) of anaprimes before 100_000_000: 4333 members:
First: 12_345_769 Last: 97_654_321
 
Largest group(s) of anaprimes before 1_000_000_000: 26519 members:
First: 102_345_697 Last: 976_542_103
</pre>
 
256

edits