id/email
password
forgot password | create account
about | help | code help+videos | done | prefs
CodingBat code practice

 

david.white@denison.edu cs109fall2014 > sieve
prev  |  next  |  chance

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)

def sieve(n):

Editor font size %:
Shorter output


Forget It! -- delete my code for this problem

Progress graphs:
 Your progress graph for this problem
 Random user progress graph for this problem
 Random Epic Progress Graph

Python Help

Copyright Nick Parlante 2017 - privacy