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.
Solution Approach
In this problem of Summation of primes till 1 million, we are supposed to find the sum of all the prime numbers in the range of 1 to 1 million.
We are given a range of numbers to which we have to find the prime numbers. This makes it the best scenario to use the Sieve of Eratosthenes method of finding prime numbers. We will essentially take numbers from 1 to 1 million and eliminate the numbers if they are divisible by 2, 3, 5, and so on. This process is repeated till 1000 as 1000 is the root of 1 million. After we identified the prime numbers by eliminating all the non-prime ones we just have to add them. The sum (upper bound will be 20000002) will be lesser than the integer’s capacity hence we can use an integer to store the value.
The time complexity of this approach is O(N log N) as we iterate through the numbers once and with each iteration we have fewer numbers to iterate through. The space complexity is 1 million to store all the data but it is constant i.e we know beforehand how much space is required, hence O(1).
Coming to the code of this approach we will have to initialize an array having 1 million space with the initial value is true. We also have to have a variable to store the sum. Secondly, we use the Sieve of Eratosthenes method to eliminate all the non-prime numbers by marking their position as false. This process is repeated till the square root of 1 million. After that, the array positions which are prime numbers will have true as their value. In the end, we will add those positions to get the final result.
Solution Code
Java Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | class Solution { private static final int LIMIT = 1000000; private static long sieveOfEratosthenes(int n) { long sumOfPrimes = 0; boolean prime[] = new boolean[n+1]; for(int i=0;i<=n;i++) prime[i] = true; for(int p = 2; p*p <=n; p++) { if(prime[p] == true) { for(int i = p*p; i <= n; i += p) prime[i] = false; } } for(int i = 2; i <= n; i++) { if(prime[i] == true) sumOfPrimes += i; } return sumOfPrimes; } public static void main(String args[]) { System.out.println(sieveOfEratosthenes(LIMIT)); } } |
Python Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | def SieveOfEratosthenes(n): sum_of_primes = 0 prime = [True for i in range(n + 1)] p = 2 while (p * p <= n): if (prime[p] == True): for i in range(p * 2, n + 1, p): prime[i] = False p += 1 prime[0]= False prime[1]= False for p in range(n + 1): if prime[p]: sum_of_primes += p return sum_of_primes if __name__=='__main__': LIMIT = 1000000 print(SieveOfEratosthenes(LIMIT)) |
For more Project Euler explained solutions visit Project Euler Detailed Solutions.
For Leetcode detailed solutions go to Leetcode Detailed Solutions.
If you like capture the flag challenges visit here.
Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page I will surely respond. Happy Coding.