about | help | code help+videos | done | prefs |
Write a function sieve(n) which implements the Sieve of Eratosthenes to determine all the prime numbers less than or equal to n. Your code should produce a list L of prime numbers less than n. Your code should return list2string(L) and thus must include the following code: The hint is to create a helper list H of Booleans such that H[k] is True if and only if k is prime. Then, once you have this list you can use a for-loop to go through H and put k into L if and only if H[k] is True. To make H, start by assuming 0 and 1 are not prime. For every number k between 2 and n-1 you could check if k is currently considered to be prime. If so then that means 2*k, 3*k, 4*k, etc cannot be prime. So set L[2*k], L[3*k], etc to be False but leave L[k] as True. You can iterate through all numbers between 2 and n-1, or you could be more clever and iterate through less of them (can you see how many are needed?). You may assume n is greater than 5. sieve(7) → '2 3 5 7 ' sieve(12) → '2 3 5 7 11 ' sieve(32) → '2 3 5 7 11 13 17 19 23 29 31 ' ...Save, Compile, Run (ctrl-enter) |
Progress graphs:
Your progress graph for this problem
Random user progress graph for this problem
Random Epic Progress Graph
Copyright Nick Parlante 2017 - privacy