Composite numbers k with no single digit factors whose factors are all substrings of k: Difference between revisions
Composite numbers k with no single digit factors whose factors are all substrings of k (view source)
Revision as of 17:02, 14 May 2023
, 1 year agoCreated Nim solution.
(Created Nim solution.) |
|||
Line 349:
{{out}}
<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}}==
| |||