Databases
StackOverflow2013
Postsdbo
POExplanation needed for sum of prime below n numbers
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POExplanation needed for sum of prime below n numbers
    text
    copied!<p>Today I solved a problem given in <a href="http://projecteuler.net/" rel="nofollow">Project Euler</a>, it's <a href="http://projecteuler.net/problem=10" rel="nofollow">problem number 10</a> and it took <strong>7 hrs</strong> for my python program to show the result. But in that forum itself a person named <em>lassevk</em> posted solution for this and it took only <strong>4 sec</strong>. And its not possible for me to post this question in that forum because its not a discussion forum. So, think about this if you want to mark this question as non-constructive.</p> <pre><code>marked = [0] * 2000000 value = 3 s = 2 while value &lt; 2000000: if marked[value] == 0: s += value i = value while i &lt; 2000000: marked[i] = 1 i += value value += 2 print s </code></pre> <p>If anyone understands this code please explain it as simple as possible.</p> <p>This is my code which took 7 hrs to compute (I think I also used the same logic of Sieve of Eratosthenes technique which was mentioned in answers below):</p> <pre><code>import time start = time.clock() total = 0 limit = 2000000 KnownPrime = set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]) KnownPrime.update(set([73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173])) suspected = set(range(2, limit+1)) # list of suspected prime numbers for p in KnownPrime: if p &lt;= limit: total += p suspected.difference_update(set(range(p, limit+1, p))) for i in suspected: k = i/2 if k % 2 == 0: k += 1 PrimeCheck = set(range(k, 2, -2)) PrimeCheck.difference_update(KnownPrime) for j in PrimeCheck: if i % j == 0: break if i % j: total += i print time.clock() - start print total </code></pre> <p>So, can anyone tell me why did it took that much time.</p> <p>Finally I did it here's my refactored code. Now it can show result with in 2 sec.</p> <pre><code>import math import __builtin__ sum = __builtin__.sum def is_prime(num): if num &lt; 2: return False if num == 2: return True if num % 2 == 0: return False for i in range(3, int(math.sqrt(num)) + 1, 2): if num % i == 0: return False return True def sum_prime(num): if num &lt; 2: return 0 sum_p = 2 core_primes = [] suspected = set(range(3, num + 1, 2)) for i in range(3, int(math.sqrt(num)) + 1, 2): if is_prime(i): core_primes.append(i) for p in core_primes: sum_p += p suspected.difference_update(set(range(p, num + 1, p))) return sum(suspected) + sum_p print sum_prime(2000000) </code></pre> <p>And here is the <a href="http://tinyurl.com/qby6gjh" rel="nofollow">visualization</a> for that.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload