Numbers whose count of divisors is prime: Difference between revisions
Numbers whose count of divisors is prime (view source)
Revision as of 10:16, 11 July 2021
, 2 years agoAdded Algol 68
(Added Go) |
(Added Algol 68) |
||
Line 7:
Stretch goal: (as above), but where '''n < 100,000'''.
<br><br>
=={{header|ALGOL 68}}==
Counts the divisors without using division.
<lang algol68>BEGIN # find numbers with prime divisor counts #
INT max number := 1 000;
TO 2 DO
INT max divisors := 0;
# construct a table of the divisor counts #
[ 1 : max number ]INT ndc; FOR i FROM 1 TO UPB ndc DO ndc[ i ] := 1 OD;
FOR i FROM 2 TO UPB ndc DO
FOR j FROM i BY i TO UPB ndc DO ndc[ j ] +:= 1 OD
OD;
FOR d TO max number DO
INT divisor count = ndc[ d ];
IF divisor count > max divisors THEN max divisors := divisor count FI
OD;
# sieve the primes to max divisors #
[ 1 : max divisors ]BOOL prime;
prime[ 1 ] := FALSE; prime[ 2 ] := TRUE;
FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] := TRUE OD;
FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO
IF prime[ i ] THEN FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD FI
OD;
# show the numbers with prime divisor counts #
print( ( "Numbers up to ", whole( max number, 0 ), " with odd prime divisor counts:", newline ) );
INT p count := 0;
FOR i TO UPB ndc DO
INT divisor count = ndc[ i ];
IF ODD divisor count AND prime[ divisor count ] THEN
print( ( whole( i, -8 ) ) );
IF ( p count +:= 1 ) MOD 10 = 0 THEN print( ( newline ) ) FI
FI
OD;
print( ( newline ) );
max number := 100 000
OD
END</lang>
{{out}}
<pre>
Numbers up to 1000 with odd prime divisor counts:
4 9 16 25 49 64 81 121 169 289
361 529 625 729 841 961
Numbers up to 100000 with odd prime divisor counts:
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|C++}}==
| |||