The problem statement is:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

can anybody help me with a shortest algorithm for this problem

The problem statement is:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

can anybody help me with a shortest algorithm for this problem

u can use sieve of eratosthenes and then sum all the elements that are primes…!!!

maybe this will be of some help…

2 Likes

Use sieve of eratosthenes to generate prime upto two million then add all the primes . Read this blog have much better explaination for project euler questions http://www.mathblog.dk/sum-of-all-primes-below-2000000-problem-10/

2 Likes

what will overflow???

sum of all primes upto two millinos , correct me if i am wrong ??

sry i was wrng answer will fit in long long int (142913828922).

import java.math.BigInteger;

```
public class Prime {
/*
* Input: an integer n > 1
*
* Let A be an array of bool values, indexed by integers 2 to n, initially
* all set to true.
*
* for i = 2, 3, 4, ..., while i^2 ≤ n: if A[i] is true: for j = i^2, i^2 +
* i, i^2 + 2i, ..., while j ≤ n: A[j] = false
*
* Now all i such that A[i] is true are prime.
*/
public static void main(String[] args) {
boolean[] array = new boolean[2000000];
BigInteger counter = new BigInteger("0");
for (int value = 0; value < array.length; value++) {
array[value] = true;
}
for (long int i = 2; i*i < array.length; i++) {
if (array[i]) {
long int j = i * i;
while (j > 0 && j < array.length) {
array[j] = false;
j += i;
}
}
}
for (long int i = 2; i < array.length; i++) {
if (array[i]) {
counter = counter.add(BigInteger.valueOf(i));
}
}
for (long int value = 2; value < array.length; value++) {
if(array[value]){
System.out.println(value + ", ");
}
}
System.out.println("\n" + counter);
}
}
```

Here is the code and as kunal told i used Sieve method

2 Likes

if i sum all numbers upto say a number n…then the ans is (n * (n+1))/2…here number is 2 * 10^6…that will be (10^6) * ((2*10^6)+1)…that is approx 2 * 10^12…but here we are just summing up primes…so the number will be way less than that…

and c/c++ has a datatype long long…can take upto 10^19…!!!

3 Likes

if you fail to understand ne part of the code…please do feel free to ask…

thank you very much…

1 Like

Why use BigInteger ??

long long takes upto 10^18

unsigned long long takes upto 10^19

long long : -9,223,372,036,854,775,807 to 9,223,372,036,854,775,807

unsigned long long : 0 to 18,446,744,073,709,551,615

here is the link…

http://crasseux.com/books/ctutorial/Integer-variables.html

for the ranges of all types of ints