Numbers whose count of divisors is prime: Difference between revisions
Content added Content deleted
(→{{header|Go}}: Takes account of Horsth's observation that only square numbers need to be tested.) |
|||
Line 219: | Line 219: | ||
73441 76729 78961 80089 83521 85849 94249 96721 97969 |
73441 76729 78961 80089 83521 85849 94249 96721 97969 |
||
</pre> |
</pre> |
||
=={{header|Nim}}== |
|||
Checking only divisors of squares (see discussion). |
|||
<lang Nim>import math, sequtils, strformat, strutils |
|||
func divCount(n: Positive): int = |
|||
var n = n |
|||
for d in 1..n: |
|||
if d * d > n: break |
|||
if n mod d == 0: |
|||
inc result |
|||
if n div d != d: |
|||
inc result |
|||
func isOddPrime(n: Positive): bool = |
|||
if n < 3 or n mod 2 == 0: return false |
|||
if n mod 3 == 0: return n == 3 |
|||
var d = 5 |
|||
while d <= sqrt(n.toFloat).int: |
|||
if n mod d == 0: return false |
|||
inc d, 2 |
|||
if n mod d == 0: return false |
|||
inc d, 4 |
|||
result = true |
|||
iterator numWithOddPrimeDivisorCount(lim: Positive): int = |
|||
for k in 1..sqrt(lim.toFloat).int: |
|||
let n = k * k |
|||
if n.divCount().isOddPrime(): |
|||
yield n |
|||
var list = toSeq(numWithOddPrimeDivisorCount(1000)) |
|||
echo &"Found {list.len} numbers between 1 and 999 whose number of divisors is an odd prime:" |
|||
echo list.join(" ") |
|||
echo() |
|||
list = toSeq(numWithOddPrimeDivisorCount(100_000)) |
|||
echo &"Found {list.len} numbers between 1 and 99_999 whose number of divisors is an odd prime:" |
|||
for i, n in list: |
|||
stdout.write &"{n:5}", if (i + 1) mod 10 == 0: '\n' else: ' ' |
|||
echo()</lang> |
|||
{{out}} |
|||
<pre>Found 16 numbers between 1 and 999 whose number of divisors is an odd prime: |
|||
4 9 16 25 49 64 81 121 169 289 361 529 625 729 841 961 |
|||
Found 79 numbers between 1 and 99_999 whose number of divisors is an odd prime: |
|||
4 9 16 25 49 64 81 121 169 289 |
|||
361 529 625 729 841 961 1024 1369 1681 1849 |
|||
2209 2401 2809 3481 3721 4096 4489 5041 5329 6241 |
|||
6889 7921 9409 10201 10609 11449 11881 12769 14641 15625 |
|||
16129 17161 18769 19321 22201 22801 24649 26569 27889 28561 |
|||
29929 32041 32761 36481 37249 38809 39601 44521 49729 51529 |
|||
52441 54289 57121 58081 59049 63001 65536 66049 69169 72361 |
|||
73441 76729 78961 80089 83521 85849 94249 96721 97969</pre> |
|||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
<lang pascal>program FacOfInteger; |
<lang pascal>program FacOfInteger; |