Sphenic numbers: Difference between revisions
Content added Content deleted
m (→{{header|AppleScript}}: Minor tidying.) |
(Added Algol 68) |
||
Line 42: | Line 42: | ||
* [[Square-free integers]] |
* [[Square-free integers]] |
||
<br> |
<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}}== |
=={{header|AppleScript}}== |