Task

Write a boolean function that tells whether a given integer is prime.



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

Use trial division.

Even numbers greater than   2   may be eliminated right away.

A loop from   3   to   √ n    will suffice,   but other loops are allowed.



Related tasks

   count in factors
   prime decomposition
   AKS test for primes
   factors of an integer
   Sieve of Eratosthenes
   factors of a Mersenne number
   trial factoring of a Mersenne number
   partition an integer X into N primes
   sequence of primes by Trial Division


100H: /* TEST FOR PRIMALITY BY TRIAL DIVISION                                */
 
   DECLARE FALSE LITERALLY '0', TRUE LITERALLY '0FFH';
   /* CP/M BDOS SYSTEM CALL                                                  */
   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$STRING( .( 0DH, 0AH, '$' ) );       END;
   PR$NUMBER: PROCEDURE( N );
      DECLARE N ADDRESS;
      DECLARE V ADDRESS, N$STR( 6 ) BYTE, W BYTE;
      N$STR( W := LAST( N$STR ) ) = '$';
      N$STR( W := W - 1 ) = '0' + ( ( V := N ) 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;
   /* INTEGER SUARE ROOT: BASED ON THE ONE IN THE PL/M FOR FROBENIUS NUMBERS */
   SQRT: PROCEDURE( N )ADDRESS;
      DECLARE ( N, X0, X1 ) ADDRESS;
      IF N <= 3 THEN DO;
          IF N = 0 THEN X0 = 0; ELSE X0 = 1;
          END;
      ELSE DO;
         X0 = SHR( N, 1 );
         DO WHILE( ( X1 := SHR( X0 + ( N / X0 ), 1 ) ) < X0 );
            X0 = X1;
         END;
      END;
      RETURN X0;
   END SQRT;
 
   IS$PRIME: PROCEDURE( N )BYTE; /* RETURNS TRUE IF N IS PRIME, FALSE IF NOT */
      DECLARE N ADDRESS;
      IF N < 2 THEN RETURN FALSE;
      ELSE IF ( N AND 1 ) = 0 THEN RETURN N = 2;
      ELSE DO;
         /* ODD NUMBER > 2                                                   */
         DECLARE I ADDRESS;
         DO I = 3 TO SQRT( N ) BY 2;
            IF N MOD I = 0 THEN RETURN FALSE;
         END;
         RETURN TRUE;
      END;
   END IS$PRIME;
 
   /* TEST THE IS$PRIME PROCEDURE                                            */
   DECLARE I ADDRESS;
   DO I = 0 TO 100;
      IF IS$PRIME( I ) THEN DO;
         CALL PR$CHAR( ' ' );
         CALL PR$NUMBER( I );
      END;
   END;
   CALL PR$NL;
 
EOF