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);
}
}
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.
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.
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.
So the sum of all the good prime numbers between 1 and 100 is 29+89=118 29 + 89 = 118 .
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 :)
@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;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With