De Polignac numbers: Difference between revisions

</pre>

=={{header|PL/M}}==

Based on the ALGOL 68 sample.

{{works with|8080 PL/M Compiler}} ... under CP/M (or an emulator)

<syntaxhighlight lang="plm">

100H: /* FIND SOME DE POLIGNAC NUMBERS - POSITIVE ODD NUMBERS THAT CAN'T BE */

/* WRITTEN AS P + 2**N FOR SOME PRIME P AND INTEGER N */

DECLARE FALSE LITERALLY '0', TRUE LITERALLY '0FFH';

/* CP/M SYSTEM CALL AND I/O ROUTINES */

BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;

PR$CHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END;

PR$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END;

PR$NL: PROCEDURE; CALL PR$CHAR( 0DH ); CALL PR$CHAR( 0AH ); END;

PR$NUMBER: PROCEDURE( N ); /* PRINTS A NUMBER IN THE MINIMUN FIELD WIDTH */

DECLARE N ADDRESS;

DECLARE V ADDRESS, N$STR ( 6 )BYTE, W BYTE;

V = N;

W = LAST( N$STR );

N$STR( W ) = '$';

N$STR( W := W - 1 ) = '0' + ( V MOD 10 );

DO WHILE( ( V := V / 10 ) > 0 );

N$STR( W := W - 1 ) = '0' + ( V MOD 10 );

END;

CALL PR$STRING( .N$STR( W ) );

END PR$NUMBER;

/* END SYSTEM CALL AND I/O ROUTINES */

DECLARE MAX$DP LITERALLY '4000', /* MAXIMUM NUMBER TO CONSIDER */

MAX$DP$PLUS$1 LITERALLY '4001'; /* MAX$DP + 1 FOR ARRAY BOUNDS */

/* SIEVE THE PRIMES TO MAX$DP */

DECLARE PRIME ( MAX$DP$PLUS$1 )BYTE;

DO;

DECLARE ( I, S ) ADDRESS;

PRIME( 0 ), PRIME( 1 ) = FALSE;

PRIME( 2 ) = TRUE;

DO I = 3 TO LAST( PRIME ) BY 2; PRIME( I ) = TRUE; END;

DO I = 4 TO LAST( PRIME ) BY 2; PRIME( I ) = FALSE; END;

DO I = 3 TO LAST( PRIME ) / 2 BY 2;

IF PRIME( I ) THEN DO;

DO S = I + I TO LAST( PRIME ) BY I; PRIME( S ) = FALSE; END;

END;

END;

END;

/* TABLE OF POWERS OF 2 UP TO MAX$DP */

DECLARE POWERS$OF$2 ( 12 )ADDRESS

INITIAL( 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 );

/* DISPLAYS A DE POLIGNAC NUMBER, IF NECESSARY */

SHOW$DE$POLIGNAC: PROCEDURE( DP$NUMBER );

DECLARE ( DP$NUMBER ) ADDRESS;

CALL PR$CHAR( ' ' );

IF DP$NUMBER < 10 THEN CALL PR$CHAR( ' ' );

IF DP$NUMBER < 100 THEN CALL PR$CHAR( ' ' );

IF DP$NUMBER < 1000 THEN CALL PR$CHAR( ' ' );

CALL PR$NUMBER( DP$NUMBER );

END SHOW$DE$POLIGNAC;

DECLARE ( I, P, COUNT ) ADDRESS;

DECLARE FOUND BYTE;

/* THE NUMBERS MUST BE ODD AND NOT OF THE FORM P + 2**N */

/* EITHER P IS ODD AND 2**N IS EVEN AND HENCE N > 0 AND P > 2 */

/* OR 2**N IS ODD AND P IS EVEN AND HENCE N = 0 AND P = 2 */

/* N = 0, P = 2 - THE ONLY POSSIBILITY IS 3 */

DO I = 1 TO 3 BY 2;

P = 2;

IF P + 1 <> I THEN DO;

COUNT = COUNT + 1;

CALL SHOW$DE$POLIGNAC( I );

END;

END;

/* N > 0, P > 2 */

I = 3;

DO WHILE I < MAX$DP AND COUNT < 50;

I = I + 2;

FOUND = FALSE;

P = 1;

DO WHILE NOT FOUND

AND P <= LAST( POWERS$OF$2 )

AND I > POWERS$OF$2( P );

FOUND = PRIME( I - POWERS$OF$2( P ) );

P = P + 1;

END;

IF NOT FOUND THEN DO;

CALL SHOW$DE$POLIGNAC( I );

IF ( COUNT := COUNT + 1 ) MOD 10 = 0 THEN CALL PR$NL;

END;

END;

EOF

</syntaxhighlight>

{{out}}

<pre>

1 127 149 251 331 337 373 509 599 701

757 809 877 905 907 959 977 997 1019 1087

1199 1207 1211 1243 1259 1271 1477 1529 1541 1549

1589 1597 1619 1649 1657 1719 1759 1777 1783 1807

1829 1859 1867 1927 1969 1973 1985 2171 2203 2213