patternjavaMinor
Project Euler "Largest prime factor" (#3) in Java
Viewed 0 times
javalargestprojecteulerfactorprime
Problem
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
I wrote the following code with help of some Java 8, I'll explain the equivalent to Java 7 under the code. I'd like general comments. One note to give up ahead is that I did not write a program that gives the largest prime factor, but one that gives all prime factors.
```
public class Problem3 extends Problem> {
private final long number;
public Problem3(final long number) {
this.number = number;
}
@Override
public void run() {
long numberCopy = number;
result = new ArrayList<>();
while (numberCopy > 1) {
PrimeG
What is the largest prime factor of the number 600851475143 ?
I wrote the following code with help of some Java 8, I'll explain the equivalent to Java 7 under the code. I'd like general comments. One note to give up ahead is that I did not write a program that gives the largest prime factor, but one that gives all prime factors.
public class ProjectEuler {
private final static int WARMUP_COUNT = 0;
private final static int REAL_COUNT = 1;
private final List> problems = new ArrayList<>();
private void init() {
problems.add(new Problem1());
problems.add(new Problem2());
problems.add(new Problem3(600851475143L));
process();
}
private void process() {
problems.stream().forEachOrdered(new ProblemConsumer());
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
new ProjectEuler().init();
}
private class ProblemConsumer implements Consumer> {
@Override
public void accept(Problem problem) {
for (int i = 0; i < WARMUP_COUNT; i++) {
problem.run();
}
System.gc();
long start = System.nanoTime();
for (int i = 0; i < REAL_COUNT; i++) {
problem.run();
}
double average = (System.nanoTime() - start) * 1.0d / REAL_COUNT;
String result = problem.getResult();
System.out.println(problem.getName() + ": " + result + " (" + String.format("%.5f", (average / 1_000_000.0)) + " ms" + ")");
}
}
}```
public class Problem3 extends Problem> {
private final long number;
public Problem3(final long number) {
this.number = number;
}
@Override
public void run() {
long numberCopy = number;
result = new ArrayList<>();
while (numberCopy > 1) {
PrimeG
Solution
Actually, your iterator is two iterators - one for the known primes (from previous 'warmups'), and one for unknown primes. Your known prime iterator's choice of implementation looks a bit cumbersome - you could have used a simple list of
Regarding your benchmark, I believe that 'warming up' is a little like cheating... you are caching the results in your static array. If you wanted to have a high-performant solution, you could have pre-calculated the first 1,000,000 primes, saved them to a file, and read them at the beginning of the procedure... :P
Long, and iterate over it:private final static List KNOWN_PRIMES = new LinkedList();
private Iterator knownPrimeIterator = KNOWN_PRIMES.iterator();
private long lastResult = 1;
public long nextLong() {
if (knownPrimeIterator != null && knownPrimeIterator.hasNext()) {
lastResult = knownPrimeIterator.next().toLong();
} else {
knownPrimeIterator = null;
lastResult = findNextPrime(lastResult+1);
KNOWN_PRIMES.add(new Long(lastResult));
}
return lastResult;
}
private long findNextPrime(long startFrom) {
// whatever here...
}Regarding your benchmark, I believe that 'warming up' is a little like cheating... you are caching the results in your static array. If you wanted to have a high-performant solution, you could have pre-calculated the first 1,000,000 primes, saved them to a file, and read them at the beginning of the procedure... :P
Code Snippets
private final static List<Long> KNOWN_PRIMES = new LinkedList<Long>();
private Iterator<Long> knownPrimeIterator = KNOWN_PRIMES.iterator();
private long lastResult = 1;
public long nextLong() {
if (knownPrimeIterator != null && knownPrimeIterator.hasNext()) {
lastResult = knownPrimeIterator.next().toLong();
} else {
knownPrimeIterator = null;
lastResult = findNextPrime(lastResult+1);
KNOWN_PRIMES.add(new Long(lastResult));
}
return lastResult;
}
private long findNextPrime(long startFrom) {
// whatever here...
}Context
StackExchange Code Review Q#42609, answer score: 6
Revisions (0)
No revisions yet.