More efficient way for this? [closed]

Question

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.

Closed 9 years ago.

I am wondering if there is a more efficient way to run this program?

It runs fine for lower numbers, but as you increase, so does the time - exponentially. So a number like 1000000 takes forever

import java.util.*;

public class SumOfPrimes {

public static void main(String args[]) {
    Scanner in = new Scanner(System.in);
    long number = 0;

    System.out.println("This program outputs the sum of the primes of a given number.");
    System.out.print("Please enter a number: ");
    number = in.nextLong();

    System.out.println("The sum of the primes below "+number+" is: "+sumOfPrimes(number));
}

public static long sumOfPrimes(long n){
    long currentNum = 2;
    long sum = 0;
    if (n > 2){
        sum = sum + 2;
    }

    while (currentNum <= n) {
        if (currentNum % 2 != 0 && isPrime(currentNum)) {
            sum = sum + currentNum;
        }
        currentNum++;
    }
return sum;
}

public static boolean isPrime(long currentNum){
    boolean primeNumber = true;

    for (long test = 2; test < currentNum; test++) {
        if ((currentNum % test) == 0){
            primeNumber = false;
        }
    }

return primeNumber;
}
}

Answer 1

There are better prime-finding algorithms, but as a quick fix, you only need to test factors up through the square root of the current number, because if you find a factor above the square root, then you should have found a factor below the square root.

long stop = (long) Math.sqrt(currentNum);
for (long test = 2; test <= stop ; test++) {

Additionally, break out of the loop and return false if you have found a factor and thus proven the number composite.

If more efficiency is desired, you can implement the Sieve of Eratosthenes so that you only check possible factors that are themselves prime.

Answer 2

Use Eratosthenes Sievie: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes You will find all primes below given number in O(n log n log n) and you will need to go once over whole table.

Answer 3

You really should store a set of prime numbers every time you find one, so you avoid dividing by all the numbers every time.

This thing: currentNum % 2 != 0 could be written as currentNum & 1.

Also your algorithm is wrong, try giving 3 as input.

Answer 4

i had written one.i can not make sure all is right.i have tested 1000000 in my machine,it just taken 31 ms. the memory require:1000000*1bytes=1mb

public class FindPrime {

/**
 * @param args
 */
public static void main(String[] args) {
    long begin=System.currentTimeMillis();
    System.out.println(findPrime(1000000));

    System.out.println("cost time="+(System.currentTimeMillis()-begin)+"ms");

}

public static long findPrime(int max){
    boolean data[]=new boolean[max+1];
    long sum=0;
    int stop=(int) Math.sqrt(max);
    for(int i=2;i<=stop;i++){
        if(data[i]==false){
            sum+=i;

            int index=i+i;
            while(index<=max){
                data[index]=true;
                index=index+i;
            }
            //System.out.println(i);
        }
    }

    stop=stop+1;

    for(;stop<=max;stop++){
        if(data[stop]==false){
            sum+=stop;
            //System.out.println(stop);
        }
    }

    return sum;
}

}