Blum integer: Difference between revisions

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.

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.

BEGIN # find Blum integers, semi-primes where both factors are 3 mod 4 #

Line 35:

Line 36:

FOR i TO UPB upfc DO upfc[ i ] := 0; lpf[ i ] := 1 OD;

FOR i FROM 2 TO UPB upfc OVER 2 DO

~~FOR~~ ~~j FROM~~ i + i ~~BY i TO UPB upfc~~ DO

IF upfc[ i ] = 0 THEN

~~upfc[~~ j ] +:= 1;

FOR j FROM i + i BY i TO UPB upfc DO

~~lpf[~~ j ] := i

upfc[ j ] +:= 1;

OD

lpf[ j ] := i

OD

FI

OD;

# returns TRUE if n is a Blum integer, FALSE otherwise #

PROC is blum = ( INT n )BOOL:

Line 71:

Line 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 WHILE b count < 400 000 DO

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:

Line 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 ( i OVER lpf[ i ] ~~) MOD 4~~ = 3 THEN

IF upfc[ i OVER lpf[ i ] ] = 0 THEN

# and ~~so is~~ the other ~~one~~ #

# and the other prime factor is unique (e.g. not 3^3) #

b count +:= 1;

last count[ i MOD 10 ] +:= 1;