Write a Python function called sieve of E_sum that takes an integer argument N a
ID: 3726554 • Letter: W
Question
Write a Python function called sieve of E_sum that takes an integer argument N and uses the Sieve of Eratosthenes to return a tuple of both the number of primes less than or equal to N as well as the sum of all primes less than or equal to N (in that order). Example:sieve of E sum(10)(4,17) Example: sieve-of-E-sun( 100000)-(9592, 45396537) This problem has a timeout limit of 1 second and a memory usage limit of 1MB, so be sure to write semi-efficient code! The values of N in each test-case satisfy 2 N 1000000 For example Test print (sieve_of E_sum(10)) (4, 17) print(sieve_of_E_sum (1000)) (168, 76127) Result Answer: (penalty regime: 0 %)Explanation / Answer
"""
Run this code in http://pythontutor.com to get visual working of this code
"""
def sieve_of_E_sum(upperLimit):
count = 0
sum = 0
limitN = upperLimit+1 #to increase the upperLimit by to include last element
not_prime = set() #instead of array we use here set to store non prime numbers
#so as to skip pre-determinenon prime numbers
primes = [] #list of prime numbers if required
for i in range(2, limitN):
if i in not_prime: #initially empty used to skip the non prime numbers
continue
for f in range(i*i, limitN, i): # loop to determine non prime numbers
not_prime.add(f)
count += 1 #count the prime numbers
sum += i #adding the primes
primes.append(i)
return (count,sum)
print( sieve_of_E_sum(1000000))
------------------------------------------------
output:
(78498, 37550402023)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.