Hey guys,
Hope you all are doing great. I am back with another problem of Project Euler on
Hope you liked this post.
Do let me know about any improvements i can incorporate to anything in the blog.
Till Then...Cheers!!
Hope you all are doing great. I am back with another problem of Project Euler on
The sum of the primes below is
Find the sum of all the primes not greater than given .
Input Format
The first line contains an integer i.e. number of the test cases.
The next lines will contains an integer .
The first line contains an integer i.e. number of the test cases.
The next lines will contains an integer .
Output Format
Print the value corresponding to each test case in separate line.
Print the value corresponding to each test case in separate line.
Constraints
Sample Input
2
5
10
Sample Output
10
17Algorithm:
The Sieve of Eratosthenes is a simple algorithm that finds the prime numbers up to a given integer. Implement this algorithm, with the only allowed optimization that the outer loop can stop at the square root of the limit, and the inner loop may start at the square of the prime just found. That means especially that you shouldn't optimize by using pre computed wheels, i.e. don't assume you need only to cross out odd numbers (wheel based on 2), numbers equal to 1 or 5 modulo 6 (wheel based on 2 and 3), or similar wheels based on low primes.
Odds-only version of the array sieve above
The below code uses only odd composite operations (for a factor of over two) and because it has been optimized to use slice operations for composite number culling to avoid extra work by the interpreter
Program:
def primes2(limit): if limit < 2: return [] if limit < 3: return [2] lmtbf = (limit - 3) // 2 buf = [True] * (lmtbf + 1) for i in range((int(limit ** 0.5) - 3) // 2 + 1): if buf[i]: p = i + i + 3 s = p * (i + 1) + i buf[s::p] = [False] * ((lmtbf - s) // p + 1) return sum([2] + [i + i + 3 for i, v in enumerate(buf) if v]) t=input() while(t>0): print primes2(input()) t-=1
Hope you liked this post.
Do let me know about any improvements i can incorporate to anything in the blog.
Till Then...Cheers!!
Add a comment