Untouchable numbers: Difference between revisions
Content added Content deleted
MaiconSoft (talk | contribs) (Added Delphi example) |
|||
Line 622: | Line 622: | ||
The count of untouchable numbers ≤ 1000000 is: 150232 |
The count of untouchable numbers ≤ 1000000 is: 150232 |
||
</pre> |
</pre> |
||
=={{header|Nim}}== |
|||
I borrowed some ideas from Go version, but keep the limit to 100_000 as in Wren version. |
|||
<lang Nim>import math, strutils |
|||
const |
|||
Lim1 = 100_000 # Limit for untouchable numbers. |
|||
Lim2 = 14 * Lim1 # Limit for computation of sum of divisors. |
|||
proc sumdiv(n: uint): uint = |
|||
## Return the sum of the strict divisors of "n". |
|||
result = 1 |
|||
let r = sqrt(n.float).uint |
|||
let k = if (n and 1) == 0: 1u else: 2u |
|||
for d in countup(k + 1, r, k): |
|||
if n mod d == 0: |
|||
result += d |
|||
let q = n div d |
|||
if q != d: result += q |
|||
var |
|||
isSumDiv: array[1..Lim2, bool] |
|||
isPrime: array[1..Lim1, bool] |
|||
# Fill both sieves in a single pass. |
|||
for n in 1u..Lim2: |
|||
let s = sumdiv(n) |
|||
if s <= Lim2: |
|||
isSumDiv[s] = true |
|||
if s == 1 and n <= Lim1: |
|||
isPrime[n] = true |
|||
isPrime[1] = false |
|||
# Build list of untouchable numbers. |
|||
var list = @[2, 5] |
|||
for n in countup(6, Lim1, 2): |
|||
if not (isSumDiv[n] or isPrime[n - 1] or isPrime[n - 3]): |
|||
list.add n |
|||
echo "Untouchable numbers ≤ 2000:" |
|||
var count, lcount = 0 |
|||
for n in list: |
|||
if n <= 2000: |
|||
stdout.write ($n).align(5) |
|||
inc count |
|||
inc lcount |
|||
if lcount == 20: |
|||
echo() |
|||
lcount = 0 |
|||
else: |
|||
if lcount > 0: echo() |
|||
break |
|||
const CountMessage = "There are $1 untouchable numbers ≤ $2." |
|||
echo CountMessage.format(count, 2000), '\n' |
|||
count = 0 |
|||
var lim = 10 |
|||
for n in list: |
|||
if n > lim: |
|||
echo CountMessage.format(count, lim) |
|||
lim *= 10 |
|||
inc count |
|||
if lim == Lim1: |
|||
# Emit last message. |
|||
echo CountMessage.format(count, lim)</lang> |
|||
{{out}} |
|||
<pre>Untouchable numbers ≤ 2000: |
|||
2 5 52 88 96 120 124 146 162 188 206 210 216 238 246 248 262 268 276 288 |
|||
290 292 304 306 322 324 326 336 342 372 406 408 426 430 448 472 474 498 516 518 |
|||
520 530 540 552 556 562 576 584 612 624 626 628 658 668 670 708 714 718 726 732 |
|||
738 748 750 756 766 768 782 784 792 802 804 818 836 848 852 872 892 894 896 898 |
|||
902 926 934 936 964 966 976 982 996 1002 1028 1044 1046 1060 1068 1074 1078 1080 1102 1116 |
|||
1128 1134 1146 1148 1150 1160 1162 1168 1180 1186 1192 1200 1212 1222 1236 1246 1248 1254 1256 1258 |
|||
1266 1272 1288 1296 1312 1314 1316 1318 1326 1332 1342 1346 1348 1360 1380 1388 1398 1404 1406 1418 |
|||
1420 1422 1438 1476 1506 1508 1510 1522 1528 1538 1542 1566 1578 1588 1596 1632 1642 1650 1680 1682 |
|||
1692 1716 1718 1728 1732 1746 1758 1766 1774 1776 1806 1816 1820 1822 1830 1838 1840 1842 1844 1852 |
|||
1860 1866 1884 1888 1894 1896 1920 1922 1944 1956 1958 1960 1962 1972 1986 1992 |
|||
There are 196 untouchable numbers ≤ 2000. |
|||
There are 2 untouchable numbers ≤ 10. |
|||
There are 5 untouchable numbers ≤ 100. |
|||
There are 89 untouchable numbers ≤ 1000. |
|||
There are 1212 untouchable numbers ≤ 10000. |
|||
There are 13863 untouchable numbers ≤ 100000.</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |