Task

Write a boolean function that tells whether a given integer is prime using Wilson's theorem.

By Wilson's theorem, a number p is prime if and only if p divides (p - 1)! + 1.

Remember that 1 and all non-positive integers are not prime.



See also

 Cut-the-knot: Wilson's theorem.
 Wikipedia: Wilson's theorem


100H: /* FIND PRIMES USING WILSON'S THEOREM:                                */
      /*      P IS PRIME IF ( ( P - 1 )! + 1 ) MOD P = 0                    */
 
   DECLARE FALSE LITERALLY '0';
 
   BDOS: PROCEDURE( FN, ARG ); /* CP/M BDOS SYSTEM CALL */
      DECLARE FN BYTE, ARG ADDRESS;
      GOTO 5;
   END BDOS;
   PRINT$CHAR:   PROCEDURE( C ); DECLARE C BYTE;    CALL BDOS( 2, C ); END;
   PRINT$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END;
   PRINT$NUMBER: PROCEDURE( N );
      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 PRINT$STRING( .N$STR( W ) );
   END PRINT$NUMBER;
 
   /* RETURNS TRUE IF P IS PRIME BY WILSON'S THEOREM, FALSE OTHERWISE       */
   /*         COMPUTES THE FACTORIAL MOD P AT EACH STAGE, SO AS TO ALLOW    */
   /*         FOR NUMBERS WHOSE FACTORIAL WON'T FIT IN 16 BITS              */
   IS$WILSON$PRIME: PROCEDURE( P )BYTE;
      DECLARE P ADDRESS;
      IF P < 2 THEN RETURN FALSE;
      ELSE DO;
         DECLARE ( I, FACTORIAL$MOD$P ) ADDRESS;
         FACTORIAL$MOD$P = 1;
         DO I = 2 TO P - 1;
            FACTORIAL$MOD$P = ( FACTORIAL$MOD$P * I ) MOD P;
         END;
         RETURN FACTORIAL$MOD$P = P - 1;
      END;
   END IS$WILSON$PRIME;
 
   DECLARE I ADDRESS;
   DO I = 1 TO 100;
      IF IS$WILSON$PRIME( I ) THEN DO;
         CALL PRINT$CHAR( ' ' );
         CALL PRINT$NUMBER( I );
      END;
   END;
 
EOF