Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Project Euler #10 I made this method off the idea off of Project Euler's #10 of finding the sum of all primes up to two million, and made the method compatible with any limit you enter in the parameters. I started out doing the obvious thing and going through each number and finding if it was divisible by anything other than itself and 1, but ra…
public class SumOfPrimes {
public SumOfPrimes(){
System.out.println(sum(2000000)); //running the sum of primes limit to 2,000,000 [For Project Euler's answer]
}
public long sum(int limit){ //Project Euler wanted it for 2,000,000 but this method can do it for any limit given
boolean[] boolPrimes = new boolean[limit]; //initializing an array of booleans to the limit
boolPrimes[0] = false; //I know 0 isn't a prime
boolPrimes[1] = false;// I know 1 isn't a prime
for(int i = 2; i < boolPrimes.length; ++i){ //setting every value after boolPrimes[0] & boolPrimes[1] equal to true
boolPrimes[i] = true;
}
for(int i = 2; i <= Math.sqrt(limit); ++i){ //every non-prime number can be stated as i*i + ni
int counter = 0; //takes place of n
int j = i*i; // making j not a prime
if(boolPrimes[i]){ //by doing this if-statement, it cancels out going through every single number from 2 -> limit
while(j < limit){ //making sure not to go out of bounds in the boolPrime array
// System.out.println("i = " + i);
// System.out.println("Setting j to not prime = " + j);
boolPrimes[j] = false; //setting non-prime to false in the array
counter++;
j = i + counter*i; //now setting j to the next non-prime number based off the prime number (i)
}
}
}
long sum = 0;
for(int i = 0; i < limit; ++i){
if(boolPrimes[i]){ //if this number is prime
// System.out.println("i is prime = " + (i));
sum += (i); //adds prime number to the sum
}
}
return sum;
}
public static void main(String[] args){
SumOfPrimes sum = new SumOfPrimes();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment