Hey guys, 
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 .
Output Format
Print the value corresponding to each test case in separate line.
Constraints

Sample Input
2
5
10
Sample Output
10
17

Algorithm:

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!!


0

Add a comment

Popular Posts
Popular Posts
print ("About Me")
print ("About Me")
My Photo
HYDERABAD, Telangana, India
Blog.History(All)
Labels
Total Pageviews
Total Pageviews
21466
About Me
About Me
Loading
Dynamic Views theme. Powered by Blogger. Report Abuse.