-- (c) Copyright - See License.txt

--

namespace primes

--****

-- == Prime Numbers

-- **Page Contents**

--

-- <>

include std/search.e

--****

-- === Routines

--

--**

-- Returns all the prime numbers below some threshold, with a cap on computation time.

--

-- Parameters:

-- # ##max_p## : an integer, the last prime returned is the next prime after or on this value.

-- # ##time_out_p## : an atom, the maximum number of seconds that this function can run for.

-- The default is 10 (ten) seconds.

--

-- Returns:

-- A **sequence**, made of prime numbers in increasing order. The last value is

-- the next prime number that falls on or after the value of ##max_p##.

--

-- Comments:

-- * The returned sequence contains all the prime numbers less than its last element.

--

-- * If the function times out, it may not hold all primes below ##max_p##,

-- but only the largest ones will be absent. If the last element returned is

-- less than ##max_p## then the function timed out.

--

-- * To disable the timeout, simply give it a negative value.

--

-- Example 1:

--

-- ? calc_primes(1000, 5)

-- -- On a very slow computer, you may only get all primes up to say 719.

-- -- On a faster computer, the last element printed out will be 997.

-- -- This call will never take longer than 5 seconds.

--

--

-- See Also:

-- [[:next_prime]] [[:prime_list]]

sequence result_

integer candidate_

integer pos_

atom time_out_

integer maxp_

integer maxf_

integer maxf_idx

integer next_trigger

-- First we check to see if we have already got the requested value.

end if

-- Already got it.

end if

-- Record the largest known prime (so far) and its index.

-- Calculate the largest possible factor for the largest known prime, and its index.

end if

-- Calculate what the trigger is for when we need to go to the next maximum factor value.

-- Pre-allocate space for the new values. This allocates more than we will

-- need so the return value takes a slice up to the last stored prime.

-- Calculate when we must stop running. A negative value is really equivalent

-- to a little over three years from now.

else

end if

-- As this could run for a significant amount of time,

-- yield to any other tasks that might be ready.

-- Get the next candidate value to examine.

-- If this is at or past the factor trigger point

-- pluck out the next maximum factor and calculate

-- the next trigger.

end if

-- Examine the candidate.

-- If this potential factor is larger than the 'maximum' factor

-- then we don't need to examine any more. The candidate is a prime.

end if

-- If it is divisible by any known prime then

-- we go get another candidate value.

end if

-- Store it in the result, making sure that the result sequence is larger enough.

end if

-- If the value just stored is larger or equal to the requested value

-- then we can stop running.

end if

end function

--**

-- Return the next prime number on or after the supplied number

--

-- Parameters:

-- # ##n## : an integer, the starting point for the search

-- # ##fail_signal_p## : an integer, used to signal error. Defaults to -1.

--

-- Returns:

-- An **integer**, which is prime only if it took less than 1 second

-- to determine the next prime greater or equal to ##n##.

--

-- Comments:

-- The default value of -1 will alert you about an invalid returned value,

-- since a prime not less than ##n## is expected. However, you can pass

-- another value for this parameter.

--

-- Example 1:

--

-- ? next_prime(997)

-- -- On a very slow computer, you might get -997, but 1003 is expected.

--

--

-- See Also:

-- [[:calc_primes]]

integer i

end if

end if

end if

-- Assumes that most searches will be less than about 1000

else

end if

end if

end function

--**

-- Returns a list of prime numbers.

--

-- Parameters:

-- # ##top_prime_p## : The list will end with the prime less than or equal

-- to this value. If this is zero, the current list calculated primes

-- is returned.

--

-- Returns:

-- An **sequence**, a list of prime numbers from 2 to ##top_prime_p##

--

-- Example 1:

--

-- sequence pList = prime_list(1000)

-- -- pList will now contain all the primes from 2 up to the largest less than or

-- -- equal to 1000.

--

--

-- See Also:

-- [[:calc_primes]], [[:next_prime]]

--

integer index_

end if

end if

end if

end function