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
Pf(2) = 2, Pf(3) = 3, So, T(3) = 2 + 3 = 5. Am I right? I do programmed to find prime factors, but could you elaborate about the current requirement. Thank you – The Coder – 2015-07-13T06:54:09.817
That is correct, I'll clarify it in the post. – Nicolás Siplis – 2015-07-13T06:55:22.957
I think this could be done relatively efficiently, using a smallest to largest sorting algorithm and then computing the sum of numbers up to length N of the sort. Doing it any other way, seems like a Greedy Method if you are working out the sum, while calculating each prime. – Killrawr – 2015-07-13T08:18:44.213
How is "60 seconds" to be measured? CPU seconds? Or single-core seconds? (A multi-threaded implementation might use 480 CPU seconds yet complete in 60 wall-clock seconds.) Run this on our own personal computer? Fastest CPU we can get our hands on? – Todd Lehman – 2015-07-13T16:15:45.333
1@ToddLehman I'm running each code in my own laptop (Sony Vaio SVF14A16CLB), so if it takes less than 60 seconds I'll increase the number and decrease it when it takes longer. – Nicolás Siplis – 2015-07-13T16:18:45.217
So if our program forks multiple threads that run in parallel and still produces the correct answer in <= 60 seconds, that is acceptable? – Todd Lehman – 2015-07-13T16:21:08.587
1Yes, as long as it runs on my own machine and outputs the correct answer in 60 seconds or less, it is acceptable. – Nicolás Siplis – 2015-07-13T16:22:03.123
How many CPU cores is the Sony Vaio SVF14A16CLB? – Todd Lehman – 2015-07-13T16:22:26.353
1It has 4 threads. – Nicolás Siplis – 2015-07-13T16:24:16.760
1Does third party Libraries are allowed? It is ok if the program is creating threads? – The Coder – 2015-07-13T17:26:00.560
Third party libraries are allowed, but make sure to clarify how to install them. Creating threads is allowed as well. – Nicolás Siplis – 2015-07-13T17:27:23.820
@NicolásSiplis It might be helpful to order the solutions in your post by
n
. – isaacg – 2015-07-13T19:10:31.757Agreed, just finished doing so. – Nicolás Siplis – 2015-07-13T19:39:34.423
I KNOW there's a formulaic answer to this of the form ${T(N) = \sum_{i \in {primes \le N}} i * COUNT(N, i)}, where ${COUNT(N, i) \approx. \frac{N - COUNT(N, i - 1)}{i}}. I kept getting thrown off by off-by-one errors that skewed the results ~_~ – sadakatsu – 2015-07-14T21:36:40.873