This was solved by brute force. I implemented a method to find the number of factors of a number by its prime factorization. Having already built up a sieve method to quickly get primes, the number of factors can be found faster this way.
PrimeNumber class:
package pba.common.number;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
public class PrimeNumbers {
private List<Integer> m_primeNumbers;
/**
* @param sizeOfSieve The upper bound to the determination of prime numbers.
*/
public PrimeNumbers(int sizeOfSieve) {
m_primeNumbers = new ArrayList<Integer>();
sieveOfEratosthenes(sizeOfSieve);
}
/**
* Calculates the number of factors for a given number by prime factorization. For example, <br>
* 28 = 2^2 * 7 <br>
* Thus the number of factors of 28 are (2+1)*(1+1) = 6.
*
* @param number The number whose number of factors are required
* @return The number of factors the given number has
*/
public int getNumberOfFactors(int number) {
int numberOfFactors = 1;
for (int prime : m_primeNumbers) {
int exponent = 0;
while (number % prime == 0) {
exponent++;
number /= prime;
}
numberOfFactors *= exponent + 1;
}
return numberOfFactors;
}
/**
* Finds the primes using the SieveOfEratosthenes method
*
* @param sizeOfSieve The upper bound till which the primes are to be calculated
*/
private void sieveOfEratosthenes(int sizeOfSieve) {
m_primeNumbers.add(2);
BitSet primeBits = new BitSet(sizeOfSieve / 2);
int primeNumberIndex = primeBits.nextClearBit(0);
int primeNumber = 2 * primeNumberIndex + 3;
while (primeNumber < sizeOfSieve) {
m_primeNumbers.add(primeNumber);
for (int i = primeNumberIndex; i < sizeOfSieve / 2; i += primeNumber)
primeBits.set(i);
primeNumberIndex = primeBits.nextClearBit(primeNumberIndex);
primeNumber = 2 * primeNumberIndex + 3;
}
}
}
Main class:
package problems_11_20;
import pba.common.number.PrimeNumbers;
public class Problem_12 {
public static void mainAnuvrat(String[] args) {
PrimeNumbers p = new PrimeNumbers(1000000);
int triangleNumber = 1;
int step = 1;
while (p.getNumberOfFactors(triangleNumber) < 500)
triangleNumber += ++step;
System.out.println(triangleNumber);
}
public static void mainProjectEuler(String[] args) {
PrimeNumbers p = new PrimeNumbers(1000000);
boolean odd = true;
int n = 1;
int numberOfFactors = 0;
int memoization = 1;
do {
if (odd) {
int temp = p.getNumberOfFactors((n + 1) / 2);
numberOfFactors = memoization * temp;
memoization = temp;
} else {
int temp = p.getNumberOfFactors(n + 1);
numberOfFactors = memoization * temp;
memoization = temp;
}
odd = !odd;
n++;
} while (numberOfFactors < 500);
n--;
System.out.println(n * (n + 1) / 2);
}
}
Project Euler did suggest an improvement on this. It says that since
and n, n+1 being co-primes, the number of divisors can be found as
This provides a lot of advantage over the previous implementation. The first being that we are now looking to find the number of factors for a smaller numbers. Secondly, the value for the n+1 can be used in the next triangle number, thus saving more computations.
Popularity: 42% [?]
Related posts:
