EiffelBase class
(HTML page generated by ISE Eiffel 4.2)
Eiffel Class
indexing
description: "Prime number properties";
status: "See notice at end of class";
names: primes;
date: "$Date: 2007-03-30 19:10:11 +0000 (Fri, 30 Mar 2007) $";
revision: "$Revision: 95354 $"
class PRIMES
inherit
COUNTABLE_SEQUENCE [INTEGER]
rename
has as is_prime
redefine
is_prime, i_th
end
feature -- Access
Smallest_prime: INTEGER is 2;
Smallest_odd_prime: INTEGER is 3;
higher_prime (n: INTEGER): INTEGER is
-- Lowest prime greater than or equal to n
do
if n <= smallest_prime then
Result := smallest_prime
else
check
n > smallest_prime
end;
from
if n \\ smallest_prime = 0 then
Result := n + 1
else
Result := n
end
until
is_prime (Result)
loop
Result := Result + smallest_prime
end
end
end;
lower_prime (n: INTEGER): INTEGER is
-- Greatest prime lower than or equal to n
require
argument_big_enough: n >= smallest_prime
do
if n = smallest_prime then
Result := smallest_prime
else
from
if n \\ smallest_prime = 0 then
Result := n - 1
else
Result := n
end
until
is_prime (Result)
loop
Result := Result - smallest_prime
end
end
end;
all_lower_primes (n: INTEGER): ARRAY [BOOLEAN] is
-- Array of n boolean values, where the
-- value at index i is true if and only if
-- i is prime.
local
i, j: INTEGER
do
from
create Result.make (1, n);
i := 3
until
i > n
loop
Result.put (true, i);
i := i + smallest_prime
end;
if n >= smallest_prime then
Result.put (true, smallest_prime)
end;
from
i := smallest_odd_prime
until
i * i > n
loop
if Result.item (i) then
from
j := i * i
until
j > n
loop
Result.put (false, j);
j := j + smallest_prime * i
end
end;
i := i + smallest_prime
end
end;
is_prime (n: INTEGER): BOOLEAN is
-- Is n a prime number?
local
to_test, divisor: INTEGER
do
if n <= 1 then
Result := false
elseif n = smallest_prime then
Result := true
elseif n \\ smallest_prime /= 0 then
from
divisor := smallest_odd_prime
until
(n \\ divisor = 0) or else (divisor * divisor >= n)
loop
divisor := divisor + smallest_prime
end;
if divisor * divisor > n then
Result := true
end
end
end;
i_th (i: INTEGER): INTEGER is
-- The i-th prime number
local
candidates: ARRAY [BOOLEAN];
found: INTEGER
do
candidates := all_lower_primes (i * i);
from
Result := 2;
found := 1
variant
i * i - Result
until
found = i
loop
Result := Result + 1;
if candidates.item (Result) then
found := found + 1
end
end
end;
end -- class PRIMES
|
