--
-- Last Revised: 2003 Dec 17
--
with
Ada.Numerics.Generic_Elementary_Functions,
interfaces;
use
Interfaces;
package body Primes is
package Ff is new Ada.Numerics.Generic_Elementary_Functions(Float);
procedure Prime_Factors (Target : in Local_Integer;
F : out Factors;
Factor_Count : out Local_Integer) is
Limit, Prime_Ptr, Factor_Ptr, Ltarget : Local_Integer;
begin
-- Ltarget and Target are the value for which this procedure is
-- to find factors.
Ltarget := Target;
-- Prime factors can be no larger than sqrt(target).
Limit := Local_Integer(Float'Floor(Ff.Sqrt(Float(Ltarget))));
Prime_Ptr := 1;
Factor_Ptr := 1;
-- Loop through primes looking for even divisors.
while Ltarget > 1 loop
if (Ltarget/P(Prime_Ptr))*P(Prime_Ptr) = Ltarget then
-- Found an even divisor so record it as a factor.
F(Factor_Ptr) := P(Prime_Ptr);
Factor_Ptr := Factor_Ptr + 1;
-- Remove the factor from the target by dividing the
-- target by the factor.
Ltarget := Ltarget/P(Prime_Ptr);
Limit := Local_Integer(Float'Floor(Ff.Sqrt(Float(Ltarget))));
loop
-- Remove all other factors of the same value from
-- target by dividing.
if (Ltarget/P(Prime_Ptr))*P(Prime_Ptr) = Ltarget then
Ltarget := Ltarget/P(Prime_Ptr);
Limit := Local_Integer(Float'Floor(Ff.Sqrt(Float(Ltarget))));
else
exit;
end if;
end loop;
exit when Ltarget = 1;
else
-- If the prime is not a factor, move to the next prime.
Prime_Ptr := Prime_Ptr + 1;
end if;
-- Record anything left as a factor.
if (P(Prime_Ptr) > Limit) and (Ltarget /= 1) then
F(Factor_Ptr) := Ltarget;
Factor_Ptr := Factor_Ptr + 1;
exit;
end if;
end loop;
-- If there was only one factor and it was the target, the that
-- does not count as a factor.
Factor_Count := Factor_Ptr - 1;
if Factor_Count = 1 then
if F(Factor_Count) = Target then
Factor_Count := 0;
end if;
end if;
end Prime_Factors;
function Is_Prime(Target : in Local_Integer) return Boolean is
Prime_Ptr, Limit : Local_Integer;
begin
-- If a target number is not prime, it must have at least one
-- factor smaller than sqrt(target).
Limit := Local_Integer(Float'Floor(Ff.Sqrt(Float(Target))));
Prime_Ptr := 1;
-- Loop through primes smaller than sqrt(target). If a prime
-- evenly divides the target then the target is not prime.
while (P(Prime_Ptr) <= Limit) and (Prime_Ptr <= Prime_Count) loop
if (Target/P(Prime_Ptr))*P(Prime_Ptr) = Target then
return False;
else
Prime_Ptr := Prime_Ptr + 1;
end if;
end loop;
-- Otherwise it is prime.
return True;
end;
end Primes;