Problem 12: Highly divisible triangular number

*Difficulty: Easy

Problem:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

How to solve:

I could only come up with two approaches. These approaches are different than each other only at the way they calculate the number of divisors of a number.
The first one use sieve Eratosthenes to create a list of prime numbers, then use that list to calculate the divisors by prime factor. The second one uses the most common way to generate all the divisors of a number. That is looping i from 1 to square root of n (n is the given number), if i is divisible by n, add 2 to the counter. Then print out the counter. But we should notice that it is not right with the perfect square number. So before we print out the counter, we check if sqrt of n to the power of 2 is equal with n , if it is, we minus 1 from counter.

The first one took 254ms, the second one took 10 time longer, about 2.5 seconds.

Implementation: Java

import java.util.Arrays;

import java.util.LinkedList;

public class Prob12 {

privatestaticboolean[] sieveEratosthenes;

privatestaticfinalintSIZE = 100000;

publicstaticvoidmain(String[] args) {

long cur = System.currentTimeMillis();

/*

int countDivisors = 0;

int triangularNumber = 1;

int ith = 1;

while(true) {

if(numberOfDivisors(triangularNumber) >= 500) {

System.out.println(triangularNumber);

System.out.println(“Took ” + (System.currentTimeMillis()-cur) + ” ms“);

//247ms

break;

}

++ith;

triangularNumber = ((ith+1)*ith)/2;

}

*/

sieveEratosthenes= new boolean[SIZE];

Arrays.fill(sieveEratosthenes, true);

for(int i = 2; i < (int)Math.sqrt(sieveEratosthenes.length); ++i) {

if(sieveEratosthenes[i])

for(int j = i*2; j < sieveEratosthenes.length; j+=i)

sieveEratosthenes[j] = false;

}

LinkedList<Integer> primeList = new LinkedList<>();

for(int i = 2; i < sieveEratosthenes.length; ++i)

if(sieveEratosthenes[i]) primeList.add(i);

int n = 1;

int i = 1;

while(true) {

if(numberOfDivisorsUsingPrimeList(primeList, n) >= 500) {

System.out.println(n);

System.out.println(“Took “ + (System.currentTimeMillis()cur) + ” ms”);

break;

}

++i;

n = ((i+1)*i)/2;

}

//http://www.mathblog.dk/triangle-number-with-more-than-500-divisors/

}

private static int numberOfDivisorsUsingPrimeList(LinkedList<Integer> primeList, int n) {

int i = 0; //first index in prime list

int divisors = 1;

int exp = 0;

while(n>1) {

int nthPrime = primeList.get(i);

if(n%nthPrime == 0) {

++exp;

n /= nthPrime;

if(n == 1) divisors*= (exp+1);

} else {

if(exp > 0) {

divisors*= (exp+1);

exp = 0;

}

++i;

}

}

return divisors;

}

privatestaticintnumberOfDivisors(int n) {

intbound = (int)Math.sqrt(n);

int divisors = 0;

for(int i = 1; i <= bound; ++i){

if(n%i==0)

divisors+=2;

}

//deal with perfect square number

if(bound*bound == n)

divisors;

return divisors;

}

}

Advertisements