Brilliant numbers: Difference between revisions
Content added Content deleted
(Added AppleScript.) |
(Created Nim solution.) |
||
Line 962: | Line 962: | ||
100140049 573929 |
100140049 573929 |
||
1000000081 7407841</pre> |
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}}== |
=={{header|Perl}}== |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |