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


 
BEGIN
 
% RETURN P MOD Q %
INTEGER FUNCTION MOD(P, Q);
INTEGER P, Q;
BEGIN
  MOD := P - Q * (P / Q);
END;
 
% RETURN INTEGER SQUARE ROOT OF N %
INTEGER FUNCTION ISQRT(N);
INTEGER N;
BEGIN
  INTEGER R1, R2;
  R1 := N;
  R2 := 1;
  WHILE R1 > R2 DO
    BEGIN
      R1 := (R1+R2) / 2;
      R2 := N / R1;
    END;
  ISQRT := R1;
END;
 
% RETURN 1 IF N IS PRIME, OTHERWISE 0 %
INTEGER FUNCTION ISPRIME(N);
INTEGER N;
BEGIN
  IF N = 2 THEN 
    ISPRIME := 1
  ELSE IF (N < 2) OR (MOD(N,2) = 0) THEN
    ISPRIME := 0
  ELSE % TEST ODD NUMBERS UP TO SQRT OF N %
    BEGIN
      INTEGER I, LIMIT;
      LIMIT := ISQRT(N);
      I := 3;
      WHILE I <= LIMIT AND MOD(N,I) <> 0 DO
        I := I + 2;
      ISPRIME := (IF I <= LIMIT THEN 0 ELSE 1);
    END;
END;  
 
% TEST FOR PRIMES IN RANGE 1 TO 50 %
INTEGER I;
WRITE("");
FOR I := 1 STEP 1 UNTIL 50 DO
  BEGIN
    IF ISPRIME(I)=1 THEN WRITEON(I,"  "); % WORKS FOR 80 COL SCREEN %
  END;
 
END
 