Prime Problems

general
1

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

2

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

maybe this will be of some help…:slight_smile:

1 Like
3

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/

1 Like
4

what will overflow???

5

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

6

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

7

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

1 Like
8

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…:slight_smile:

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

3 Likes
9

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

10

thank you very much… :slight_smile:

1 Like
11

Why use BigInteger ??

12

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

13

here is the link…
http://crasseux.com/books/ctutorial/Integer-variables.html
for the ranges of all types of ints