47 lines
2 KiB
Text
47 lines
2 KiB
Text
MODULE SemiPrimes;
|
|
IMPORT Math, Out;
|
|
|
|
(* returns TRUE if n is semi-prime, FALSE otherwise *)
|
|
(* n is semi prime if it has exactly two prime factors *)
|
|
PROCEDURE isSemiPrime( n : INTEGER ) : BOOLEAN;
|
|
VAR factor, factorCount, maxLowFactor, otherFactor : INTEGER;
|
|
BEGIN
|
|
(* We only need to consider factors between 2 and *)
|
|
(* sqrt( n ) inclusive. If there is only one of these *)
|
|
(* then it must be a prime factor and so the number *)
|
|
(* is semi prime *)
|
|
factorCount := 0;
|
|
maxLowFactor := FLOOR( Math.sqrt( FLT( ABS( n ) ) ) );
|
|
factor := 2;
|
|
WHILE ( factor <= maxLowFactor ) & ( factorCount < 2 ) DO
|
|
IF n MOD factor = 0 THEN
|
|
INC( factorCount );
|
|
(* check the factor isn't a repeated factor *)
|
|
IF n # factor * factor THEN
|
|
(* the factor isn't the square root *)
|
|
otherFactor := n DIV factor;
|
|
IF otherFactor MOD factor = 0 THEN
|
|
(* have a repeated factor *)
|
|
INC( factorCount )
|
|
END
|
|
END
|
|
END;
|
|
INC( factor );
|
|
END
|
|
RETURN factorCount = 1
|
|
END isSemiPrime;
|
|
|
|
PROCEDURE showSemiPrimes( title : ARRAY OF CHAR; fromN, toN : INTEGER );
|
|
VAR i : INTEGER;
|
|
BEGIN
|
|
Out.String( title );Out.String( ":" );Out.Ln;Out.String( " " );
|
|
FOR i := fromN TO toN DO
|
|
IF isSemiPrime( i ) THEN Out.String( " " );Out.Int( i, 0 ) END
|
|
END;
|
|
Out.Ln
|
|
END showSemiPrimes;
|
|
|
|
BEGIN
|
|
showSemiPrimes( "semi primes below 100", 1, 99 );
|
|
showSemiPrimes( "semi primes between 1670 and 1690", 1670, 1690 )
|
|
END SemiPrimes.
|