Write a function
Sieve(n)which takes a positive integer
n, and returns a list containing all primes less or equal
n, in strictly ascending order. Compute this list using the sieve of Eratosthenes. Submit your solution in a file called
Your program should be able to compute
Sieve(10^7)in under 20 seconds.
Hint: You can use the function
RootIntto compute an integer approximation of the square root of an integer (consult the manual to learn how to use it). However, it is also fine to write a solution working without it.
Hint: The function
Addmay also be useful: It can append a single element to the end of a list (again, please consult the GAP manual for details).