Sphenic numbers: Difference between revisions
Added Algol 68
m (→{{header|AppleScript}}: Minor tidying.) |
(Added Algol 68) |
||
Line 42:
* [[Square-free integers]]
<br>
=={{header|ALGOL 68}}==
{{libheader|ALGOL 68-primes}}
Assumes LONG INT is 64 bits (or larger). As with other samples, uses a prime sieve to construct the Sphenic numbers.
<br>
To run this with ALGOL 68G, a large heap sie must be specified on the ALGOL 68G command line, e.g.: <code>-heap 256M</code>.
<syntaxhighlight lang="algol68">
BEGIN # find some Sphenic numbers - numbers that are the product of three #
# distinct primes #
PR read "primes.incl.A68" PR # include prime utilities #
INT max sphenic = 1 000 000; # maximum number we will consider #
[]BOOL prime = PRIMESIEVE max sphenic;
# construct a list of the primes up to the maximum prime to consider #
[]INT prime list = EXTRACTPRIMESUPTO max sphenic FROMPRIMESIEVE prime;
# form a sieve of Sphenic numbers #
[ 1 : max sphenic ]BOOL sphenic;
FOR i TO UPB sphenic DO sphenic[ i ] := FALSE OD;
INT root max = ENTIER sqrt( max sphenic );
FOR i WHILE LONG INT p1 = prime list[ i ];
p1 < root max
DO
FOR j FROM i + 1 WHILE LONG INT p2 = prime list[ j ];
LONG INT p1p2 = p1 * p2;
( p1p2 * p2 ) < max sphenic
DO
FOR k FROM j + 1 WHILE LONG INT s = p1p2 * prime list[ k ];
s <= max sphenic
DO
sphenic[ SHORTEN s ] := TRUE
OD
OD
OD;
# show the Sphenic numbers up to 1 000 #
print( ( "Sphenic numbers up to 1 000:", newline ) );
INT s count := 0;
FOR i TO 1 000 DO
IF sphenic[ i ] THEN
print( ( whole( i, -5 ) ) );
IF ( s count +:= 1 ) MOD 15 = 0 THEN print( ( newline ) ) FI
FI
OD;
print( ( newline ) );
# show the Sphenic triplets up to 10 000 #
print( ( "Sphenic triplets up to 10 000:", newline ) );
INT t count := 0;
FOR i TO 10 000 - 2 DO
IF sphenic[ i ] AND sphenic[ i + 1 ] AND sphenic[ i + 2 ] THEN
print( ( " (", whole( i, -4 )
, ", ", whole( i + 1, -4 )
, ", ", whole( i + 2, -4 )
, ")"
)
);
IF ( t count +:= 1 ) MOD 3 = 0 THEN print( ( newline ) ) FI
FI
OD;
# count the Sphenic numbers and Sphenic triplets and find specific #
# Sphenic numbers and triplets #
s count := t count := 0;
INT s200k := 0;
INT t5k := 0;
FOR i TO UPB sphenic - 2 DO
IF sphenic[ i ] THEN
s count +:= 1;
IF s count = 200 000 THEN
# found the 200 000th Sphenic number #
s200k := i
FI;
IF sphenic[ i + 1 ] AND sphenic[ i + 2 ] THEN
t count +:= 1;
IF t count = 5 000 THEN
# found the 5 000th Sphenic triplet #
t5k := i
FI
FI
FI
OD;
FOR i FROM UPB sphenic - 1 TO UPB sphenic DO
IF sphenic[ i ] THEN
s count +:= 1
FI
OD;
print( ( newline ) );
print( ( "Number of Sphenic numbers up to 1 000 000: ", whole( s count, -8 ), newline ) );
print( ( "Number of Sphenic triplets up to 1 000 000: ", whole( t count, -8 ), newline ) );
print( ( "The 200 000th Sphenic number: ", whole( s200k, 0 ) ) );
# factorise the 200 000th Sphenic number #
INT f count := 0;
FOR i WHILE f count < 3 DO
INT p = prime list[ i ];
IF s200k MOD p = 0 THEN
print( ( IF ( f count +:= 1 ) = 1 THEN ": " ELSE " * " FI
, whole( p, 0 )
)
)
FI
OD;
print( ( newline ) );
print( ( "The 5 000th Sphenic triplet: "
, whole( t5k, 0 ), ", ", whole( t5k + 1, 0 ), ", ", whole( t5k + 2, 0 )
, newline
)
)
END
</syntaxhighlight>
{{out}}
<pre>
Sphenic numbers up to 1 000:
30 42 66 70 78 102 105 110 114 130 138 154 165 170 174
182 186 190 195 222 230 231 238 246 255 258 266 273 282 285
286 290 310 318 322 345 354 357 366 370 374 385 399 402 406
410 418 426 429 430 434 435 438 442 455 465 470 474 483 494
498 506 518 530 534 555 561 574 582 590 595 598 602 606 609
610 615 618 627 638 642 645 646 651 654 658 663 665 670 678
682 705 710 715 730 741 742 754 759 762 777 782 786 790 795
805 806 814 822 826 830 834 854 861 874 885 890 894 897 902
903 906 915 935 938 942 946 957 962 969 970 978 986 987 994
Sphenic triplets up to 10 000:
(1309, 1310, 1311) (1885, 1886, 1887) (2013, 2014, 2015)
(2665, 2666, 2667) (3729, 3730, 3731) (5133, 5134, 5135)
(6061, 6062, 6063) (6213, 6214, 6215) (6305, 6306, 6307)
(6477, 6478, 6479) (6853, 6854, 6855) (6985, 6986, 6987)
(7257, 7258, 7259) (7953, 7954, 7955) (8393, 8394, 8395)
(8533, 8534, 8535) (8785, 8786, 8787) (9213, 9214, 9215)
(9453, 9454, 9455) (9821, 9822, 9823) (9877, 9878, 9879)
Number of Sphenic numbers up to 1 000 000: 206964
Number of Sphenic triplets up to 1 000 000: 5457
The 200 000th Sphenic number: 966467: 17 * 139 * 409
The 5 000th Sphenic triplet: 918005, 918006, 918007
</pre>
=={{header|AppleScript}}==
| |||