Composite numbers k with no single digit factors whose factors are all substrings of k: Difference between revisions
Content added Content deleted
(Created Nim solution.) |
|||
Line 349: | Line 349: | ||
{{out}} |
{{out}} |
||
<pre>{15317, 59177, 83731, 119911, 183347, 192413, 1819231, 2111317, 2237411, 3129361, 5526173, 11610313, 13436683, 13731373, 13737841, 13831103, 15813251, 17692313, 19173071, 28118827}</pre> |
<pre>{15317, 59177, 83731, 119911, 183347, 192413, 1819231, 2111317, 2237411, 3129361, 5526173, 11610313, 13436683, 13731373, 13737841, 13831103, 15813251, 17692313, 19173071, 28118827}</pre> |
||
=={{header|Nim}}== |
|||
We use a sieve to build a list of prime factors. This is more efficient than computing the list of prime factors on the fly. |
|||
To find the 25 first elements of the sequence, the program takes about 23 seconds on an Intel Core I5-8250U 4×1.6GHz. |
|||
<syntaxhighlight lang="Nim">import std/[strformat, strutils] |
|||
const Max = 80_000_000 # Maximal value for composite number. |
|||
# Prime factors of odd numbers. |
|||
# If a number is prime, its factor list is empty. |
|||
var factors: array[0..(Max - 3) div 2, seq[uint32]] |
|||
template primeFactors(n: Natural): seq[uint32] = |
|||
factors[(n - 3) shr 1] |
|||
# Build the list of factors. |
|||
for n in countup(3u32, Max div 11, 2): |
|||
if primeFactors(n).len == 0: |
|||
# "n" is prime. |
|||
for k in countup(n + n + n, Max, 2 * n): |
|||
primeFactors(k).add n |
|||
const N = 25 # Number of results. |
|||
var n = 11 * 11 |
|||
var count = 0 |
|||
while count < N: |
|||
if primeFactors(n).len > 0: |
|||
let nStr = $n |
|||
block Check: |
|||
for f in primeFactors(n): |
|||
if f < 11 or $f notin nStr: break Check |
|||
inc count |
|||
echo &"{count:2}: {insertSep($n)}" |
|||
inc n, 2 |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 1: 15_317 |
|||
2: 59_177 |
|||
3: 83_731 |
|||
4: 119_911 |
|||
5: 183_347 |
|||
6: 192_413 |
|||
7: 1_819_231 |
|||
8: 2_111_317 |
|||
9: 2_237_411 |
|||
10: 3_129_361 |
|||
11: 5_526_173 |
|||
12: 11_610_313 |
|||
13: 13_436_683 |
|||
14: 13_731_373 |
|||
15: 13_737_841 |
|||
16: 13_831_103 |
|||
17: 15_813_251 |
|||
18: 17_692_313 |
|||
19: 19_173_071 |
|||
20: 28_118_827 |
|||
21: 31_373_137 |
|||
22: 47_458_321 |
|||
23: 55_251_877 |
|||
24: 62_499_251 |
|||
25: 79_710_361 |
|||
</pre> |
|||
=={{header|Pascal}}== |
=={{header|Pascal}}== |