Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find the sum of all the primes below two million.My program doesn't work for very big numbers

This is my code for finding the sum of primes.It works good with some low numbers but if it's 2000000(2 million) it never ends.Anybody can help me?

import java.math.BigInteger;
public class Problem010{
    public static void main(String[] args) {

        BigInteger sum = new BigInteger("2");

        //for (int i=3; i<2000000; i++) {
        for(int i=3; i<10; i++){
            for (int j=2; j<i; j++){
                if (i % j == 0) 
                    break;
                else if (i == j+1){
                    sum = sum.add(BigInteger.valueOf(i));
                }
            }
        }
        System.out.println("Sum  = "+sum); 
    }
}
like image 541
Noli Avatar asked Apr 23 '15 06:04

Noli


People also ask

What is the sum of all primes below 2 million?

It's already been around 4 minutes and I'm impatient. So I google around for the solution and found a Yahoo! Answers page which says that the sum of all primes below 2 million is 142,913,828,922. That's good.

How do you find the sum of all prime numbers?

A simple solution is to traverse all numbers from 1 to n. For every number, check if it is a prime. If yes, add it to result. An efficient solution is to use Sieve of Eratosthenes to find all prime numbers from till n and then do their sum.

Can all prime numbers be expressed as a sum of two or more prime numbers?

Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and all of mathematics. It states that every even natural number greater than 2 is the sum of two prime numbers.

What is the sum of all prime numbers up to 100?

So the sum of all the good prime numbers between 1 and 100 is 29+89=118 29 + 89 = 118 .


2 Answers

your answer is 142913828922 but how?

I just changed your algorithm a little bit:

public static void main(String[] args) {

    BigInteger sum = new BigInteger("2");
    boolean isPrime = true;
    for (int i=3; i<2000000; i++) {
    double aa = Math.sqrt((double)i);
        for (int j=2; j<=aa; j++){
            if (i % j == 0){ 
                isPrime = false;
                break;
            }
        }
        if(isPrime){
            sum = sum.add(BigInteger.valueOf(i));
        }
        isPrime = true;
    }
    System.out.println("Sum  = "+sum); 
}

instead of going through all the numbers from 2 to i I just go from 2 to sqrt(i) and this improve your code running time a lot :)

like image 79
Lrrr Avatar answered Sep 29 '22 23:09

Lrrr


@Lrrr, answer is correct. But algorithm can be further optimised. Look at my isPrime algorithm. For 2 million you don't need the BigInteger.

    long sum = 2;// new BigInteger("2");
    for (int i=3; i<2000000; i++) {
        if(isPrime(i)) {
            sum = sum + i;//.add(BigInteger.valueOf(i));
        }    
    }
    System.out.println("Sum  = "+sum);

Here is isPrime method.

 static boolean isPrime(int n) {
    if (n < 2) {
        return false;
    }
    if (n == 2 || n == 3) {
        return true;
    }
    if ((n & 1) == 0 || n % 3 == 0) {
        return false;
    }
    int sqrtN = (int) Math.sqrt(n) + 1;
    for (int i = 6; i <= sqrtN; i += 6) {// loop 6 step
        if (n % (i - 1) == 0 || n % (i + 1) == 0) {
            return false;
        }
    }
    return true;
}
like image 36
Masudul Avatar answered Sep 30 '22 01:09

Masudul