Brilliant numbers: Difference between revisions
Created Nim solution.
(Added AppleScript.) |
(Created Nim solution.) |
||
Line 962:
100140049 573929
1000000081 7407841</pre>
=={{header|Nim}}==
{{trans|C++}}
{{trans|Java}}
<syntaxhighlight lang="Nim">import std/[algorithm, math, strformat, strutils]
func primes(lim: Natural): seq[Natural] =
## Build list of primes using a sieve of Erathostenes.
var composite = newSeq[bool]((lim + 1) shr 1)
composite[0] = true
for n in countup(3, int(sqrt(lim.toFloat)), 2):
if not composite[n shr 1]:
for k in countup(n * n, lim, 2 * n):
composite[k shr 1] = true
result.add 2
for n in countup(3, lim, 2):
if not composite[n shr 1]:
result.add n
func getPrimesByDigits(lim: Natural): seq[seq[Natural]] =
## Distribute primes according to their number of digits.
var p = 10
result.add @[]
for prime in primes(lim):
if prime > p:
p *= 10
if p > 10 * lim: break
result.add @[]
result[^1].add prime
let primesByDigits = getPrimesByDigits(10^9-1)
###
echo "First 100 brilliant numbers:"
var brilliantNumbers: seq[Natural]
for primes in primesByDigits:
for i in 0..primes.high:
for j in 0..i:
brilliantNumbers.add primes[i] * primes[j]
if brilliantNumbers.len >= 100: break
brilliantNumbers.sort()
for i in 0..99:
stdout.write &"{brilliantNumbers[i]:>5}"
if i mod 10 == 9: echo()
echo()
###
var power = 10
var count = 0
for p in 1..<(2 * primesByDigits.len):
let primes = primesByDigits[p shr 1]
var pos = count + 1
var minProduct = int.high
for i, p1 in primes:
let j = primes.toOpenArray(i, primes.high).lowerBound((power + p1 - 1) div p1)
let p2 = primes[i + j]
let product = p1 * p2
if product < minProduct:
minProduct = product
inc pos, j
if p1 >= p2: break
echo &"First brilliant number ⩾ 10^{p:<2} is {minProduct} at position {insertSep($pos)}"
power *= 10
if p mod 2 == 1:
inc count, primes.len * (primes.len + 1) div 2
</syntaxhighlight>
{{out}}
Most of the execution time is used to fill the sieve of Erathostenes.
<pre>First 100 brilliant numbers:
4 6 9 10 14 15 21 25 35 49
121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451
473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713
731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949
961 979 989 1003 1007 1027 1037 1067 1073 1079
1081 1121 1139 1147 1157 1159 1189 1207 1219 1241
1247 1261 1271 1273 1333 1343 1349 1357 1363 1369
First brilliant number ⩾ 10^1 is 10 at position 4
First brilliant number ⩾ 10^2 is 121 at position 11
First brilliant number ⩾ 10^3 is 1003 at position 74
First brilliant number ⩾ 10^4 is 10201 at position 242
First brilliant number ⩾ 10^5 is 100013 at position 2_505
First brilliant number ⩾ 10^6 is 1018081 at position 10_538
First brilliant number ⩾ 10^7 is 10000043 at position 124_364
First brilliant number ⩾ 10^8 is 100140049 at position 573_929
First brilliant number ⩾ 10^9 is 1000000081 at position 7_407_841
First brilliant number ⩾ 10^10 is 10000600009 at position 35_547_995
First brilliant number ⩾ 10^11 is 100000000147 at position 491_316_167
First brilliant number ⩾ 10^12 is 1000006000009 at position 2_409_600_866
First brilliant number ⩾ 10^13 is 10000000000073 at position 34_896_253_010
First brilliant number ⩾ 10^14 is 100000380000361 at position 174_155_363_187
First brilliant number ⩾ 10^15 is 1000000000000003 at position 2_601_913_448_897
First brilliant number ⩾ 10^16 is 10000001400000049 at position 13_163_230_391_313
First brilliant number ⩾ 10^17 is 100000000000000831 at position 201_431_415_980_419
</pre>
=={{header|Perl}}==
{{libheader|ntheory}}
| |||