Skip to main content

Problem 10 Project euler Solution with python

Hello friends today I have solved problem 10 on project Euler and I am here to share it with you. Let's first see the question and then we will see the solution.

Summation of primes

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.?

My first attempt to solve this problem was to use the sieve function which I have written for  Problem 7 and extend it for generating the required solution.

But what I saw was that my solution took around 1.5 seconds to execute. I was not satisfied with the result and wanted more faster solution. Surfing on internet I found Sieve of Atkins, which most people suggested for better result.

But what I found was that Sieve of Eratosthenes had better execution time compared with the Atkin's Sieve. So obviously I have finalized the solution with the Sieve of Eratosthenes.

Program

Program written using Sieve of Eratosthenes is as follows:
If you want to understand this program search on your favorite search engine for Sieve of Eratosthenes and take some time to read it. You will for sure understand the program. After you have read the program, to understand it better, take some example and iterate manually.

 If you want to download the program then you can download it from  Github Gist

 Next I will also show you the Sieve of Atkins program I have written. But the original from which I have derived my program is available on Github - Sieve of Atkin.
The program is as follows: 

#http://radiusofcircle.blogspot.com

#time module for calculating time
import time,math

#Time at the start of execution
start =time.time()

#Sieve of Atkins
#https://en.wikipedia.org/wiki/Sieve_of_Atkin
def sieve_of_atkins(limit):
 #Initial primes
 primes = [2,3]
 sieve = [False]*(limit+1)
 testingLimit = int(math.sqrt(limit))+1
 
 #For loop for generating x, y
 for x in xrange(testingLimit):
  for y in xrange(testingLimit):
   
   #n = 4x^2+y^2
   n = 4*int(x**2)+int(y**2)
   if n <= limit and (n%12 ==1 or n%12 ==5):
    sieve[n] = True
   
   #n = 3x^2+y^2
   n = 3*int(x**2)+int(y**2)
   if n<= limit and (n%12 == 7):
    sieve[n] = True
   
   #n = 3x^2-y^2
   n = 3*int(x**2) - int(y**2)
   if n<= limit and x > y and n%12 == 11:
    sieve[n] = True

 #for loop to remove all the multiples of primes
 for i in xrange(5,testingLimit):
  if sieve[i]:
   index = i**2
   while index < limit:
    sieve[index] = False
    index += i

 #for loop to create prime numbers list
 for i in xrange(2,len(sieve)):
  if sieve[i]:
   primes.append(i)
 return primes

#Printing the output
print sum(sieve_of_atkins(2000000))

#Time at the end of execution
end = time.time()

#total time for execution
print end-start
This program had an execution time of around 2.48 seconds which is greater than the execution time required for sieve of Eratosthenes.

 If you want to understand the above program then it is better to first understand the algorithm of Sieve of Atkins and then you will be good to go. If you want to some sources where you can learn are as follows:
Last but not the least: Wikipedia - Sieve of Atkins

Output

Summary

Even though this program had execution time greater than 1 second, I didn't bother because the number was 2 million which needed a lot of computation. But I have obtained the solution within 2-4 seconds for both the programs. Also I have learned something new from this problem and I am satisfied.

 I haven't explained any part of the code because it is well commented and also you can take it as an exercise where you will have to decode the code in human language. If you have any doubt or didn't understand anything then please do comment in the comment box below and I will be glad to help you.

 Please don't hesitate to comment if I have made any typo or if you want me to add any extra thing. Please Please do share your program, if your program has a different approach or if it run much faster than any of the programs I have written.

 You can also contact me if you want to.

 Thank you. Have a nice day😃.
Labels:

Popular posts from this blog

Making a quiz web app with python and flask

Edit : When you are creating a web app with h tml templates, then y ou will have to sa ve the html file in templates folder in the Current Wor ki ng Directory( CWD). If you save the file in the C W D directl y you will get a TemplateNotFound error. Thank you Udhay for pointing it out.   In this post we will create a quiz website using python . I will be using the flask framework . After reading this tutorial you will learn form submission , flask templates , python code in flask templates , shuffling the questions and options with the random module and few others.  Please note that this tutorial is not big as it seems to be. Some of the code has been rewritten to maintain consistency and also font size is somewhat big so that your eyes won't get stressed reading this tutorial. Also the content has not occupied the full width of the page. In this tutorial I am assuming that you are having a very basic understanding of the flask framework . Please refer the documentation
Read more

Problem 11 Project Euler Solution with python

Largest product in a grid In the 20×20 grid below, four numbers along a diagonal line have been marked in red. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07
Read more

Problem 60 Project Euler Solution with python

Prime pair sets The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property. Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime. This problem is j u st a brute force problem. If you have come here because you don't know the limit upto which you will h ave to gener ate the prime numbers t hen go ahe ad and t r y with 10,000 . When I first start ed solving the problem I chose 1 million(beca use most of the problem s on project E uler have this limit ), but it took very long for the computer to fin d the solution. After searching on the internet then I found many people choosing 10, 000 so I have changed my in put f rom 1 million to 10000 and the output was f ast. He
Read more