Blum integer: Difference between revisions
→{{header|ALGOL 68}}: Improved unique prime factor counting gives better performance
(→{{header|ALGOL 68}}: Improved unique prime factor counting gives better performance) |
|||
Line 26:
=={{header|ALGOL 68}}==
If running this with ALGOL 68G, you will need to specify a larger heap size with <code>-heap 256M</code> on the command line.<br>
Builds tables of the unique prime factor counts and the last prime factor to handle the stretch goal, uses prime factorisation to find the first 50 Blum integers.<br>
Note that Blum integers must be 1 modulo 4 and if one prime factor is 3 modulo 4, the other must also be.
<syntaxhighlight lang="algol68">
BEGIN # find Blum integers, semi-primes where both factors are 3 mod 4 #
Line 35 ⟶ 36:
FOR i TO UPB upfc DO upfc[ i ] := 0; lpf[ i ] := 1 OD;
FOR i FROM 2 TO UPB upfc OVER 2 DO
OD
FI
OD;
# returns TRUE if n is a Blum integer, FALSE otherwise #
PROC is blum = ( INT n )BOOL:
Line 71 ⟶ 73:
INT b count := 0;
[ 0 : 9 ]INT last count := []INT( 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 )[ AT 0 ];
FOR i FROM 21 BY 4 WHILE b count < 400 000 DO
# Blum integers must be 1 modulo 4 #
IF b count < 50 THEN
IF is blum( i ) THEN
Line 80 ⟶ 83:
FI
ELIF upfc[ i ] = 2 THEN
# two unique prime factors - could be a Blum integer #
IF lpf[ i ] MOD 4 = 3 THEN
# the last prime factor mod 4 is three #
IF
# and
b count +:= 1;
last count[ i MOD 10 ] +:= 1;
| |||