Java – project Euler: procedural optimization of question 7?
So I call myself a fairly novice programmer because I mainly focus on my school hardware rather than many computer science courses
So I solved the problem 7 of Euler project:
I managed to solve this problem in Java without a problem, but when I ran my solution, it took 8 and changed the number of seconds I want to know how to optimize this from a programming point of view, not a mathematical point of view
Are array loops and while statements mainly processing time consuming? How can this be optimized? Again, don't look for a strange mathematical equation... There are many in the solution thread
Spoiler my solution is as follows
public class PrimeNumberList {
private ArrayList<BigInteger> primesList = new ArrayList<BigInteger>();
public void fillList(int numberOfPrimes) {
primesList.add(new BigInteger("2"));
primesList.add(new BigInteger("3"));
while (primesList.size() < numberOfPrimes){
getNextPrime();
}
}
private void getNextPrime() {
BigInteger lastPrime = primesList.get(primesList.size()-1);
BigInteger currentTestNumber = lastPrime;
BigInteger modulusResult;
boolean prime = false;
while(!prime){
prime = true;
currentTestNumber = currentTestNumber.add(new BigInteger("2"));
for (BigInteger bi : primesList){
modulusResult = currentTestNumber.mod(bi);
if (modulusResult.equals(BigInteger.ZERO)){
prime = false;
break;
}
}
if(prime){
primesList.add(currentTestNumber);
}
}
}
public BigInteger get(int primeTerm) {
return primesList.get(primeTerm - 1);
}
}
Solution
Since the 10001st prime is not so large, you can use long instead of BigInteger BigInteger instance is a mature Java object. There will be a lot of overhead when creating and operating them
