Java 8: 1.8e8 2.4e8
This entry does not compare to several of the other ones already up, but I wanted to post my answer since I had fun working on this.
The main optimizations of my approach are as follow:
- Every even number has a smallest factor of 2, so these can be added for free after every odd number is processed. Basically, if you have done the work to calculate
T(N) when N % 2 == 1, you know that T(N + 1) == T(N) + 2. This allows me to start my counting at three and to increment by iteration by twos.
- I store my prime numbers in an array as opposed to a
Collection type. This more than doubled the N I can reach.
- I use the prime numbers to factor a number as opposed to performing the Sieve of Eratosthenes. This means that my memory storage is restricted almost completely to my primes array.
- I store the square root of the number for which I am trying to find the smallest factor. I tried @user1354678's approach of squaring a prime factor each time, but this cost me about than 1e7 from my score.
That's about all there is to it. My code iterates from 3 on by twos until it detects that it has hit or exceeded the time limit, at which point it spits out the answer.
package sum_of_smallest_factors;
public final class SumOfSmallestFactors {
private static class Result {
private final int number;
int getNumber() {
return number;
}
private final long sum;
long getSum() {
return sum;
}
Result(int number, long sum) {
this.number = number;
this.sum = sum;
}
}
private static final long TIME_LIMIT = 60_000_000_000L; // 60 seconds x 1e9 nanoseconds / second
public static void main(String[] args) {
SumOfSmallestFactors main = new SumOfSmallestFactors();
Result result = main.run();
int number = result.getNumber();
long sum = result.getSum();
System.out.format("T(%,d) = %,d\n", number, sum);
}
private int[] primes = new int[16_777_216];
private int primeCount = 0;
private long startTime;
private SumOfSmallestFactors() {}
private Result run() {
startClock();
int number;
long sumOfSmallestFactors = 2;
for (number = 3; mayContinue(); number += 2) {
int smallestFactor = getSmallestFactor(number);
if (smallestFactor == number) {
addPrime(number);
}
sumOfSmallestFactors += smallestFactor + 2;
}
--number;
Result result = new Result(number, sumOfSmallestFactors);
return result;
}
private void startClock() {
startTime = System.nanoTime();
}
private boolean mayContinue() {
long currentTime = System.nanoTime();
long elapsedTime = currentTime - startTime;
boolean result = (elapsedTime < TIME_LIMIT);
return result;
}
private int getSmallestFactor(int number) {
int smallestFactor = number;
int squareRoot = (int) Math.ceil(Math.sqrt(number));
int index;
int prime = 3;
for (index = 0; index < primeCount; ++index) {
prime = primes[index];
if (prime > squareRoot) {
break;
}
int remainder = number % prime;
if (remainder == 0) {
smallestFactor = prime;
break;
}
}
return smallestFactor;
}
private void addPrime(int prime) {
primes[primeCount] = prime;
++primeCount;
}
}
Running on a different system (Windows 8.1, Intel core i7 @ 2.5 GHz, 8 GB RAM) with the latest version of Java 8 has markedly better results with no code changes:
T(240,308,208) = 1,537,216,753,010,879
