# Project Euler #179 – Java

You can see the problem here: Problem #179.

Another easy question. From question 10, I learned that you can find the number of factors of a number n by first factorizing n into where p is a unique prime number. The number of factors can be found by calculating Like I mentioned in past posts, in Project Euler, a sieve is almost always better than anything else when dealing with prime numbers and that is exactly what I did.

final int LIMIT = 10000000; int[] num = new int[LIMIT + 2]; Arrays.fill(num, 1); for (int i = 2; i < LIMIT + 2; i++) { if (num[i] == 1) { num[i] = 2; //j is a variable use to keep track of when to test for the number having more than 1 copy of the prime factor for (int j = i + i, k = 2; j < LIMIT + 2; k++, j += i) { if (k == i) { int mul = 1, temp = j; while (temp % i == 0) { mul++; temp /= i; } num[j] *= mul; k = 0; } else { num[j] <<= 1; } } } } int count = 0; for (int i = 2; i < LIMIT + 1; i++) { if (num[i] == num[i + 1]) { count++; } } System.out.println(count);

This ran in 2.5 seconds on my computer.

This is the method generally use on the forum post. Using an array to keep track and dynamically generate the number of factors for each number. It finds the multiples of each number and increment the corresponding array element.

final int LIMIT = 10000000; int[] num = new int[LIMIT + 2]; Arrays.fill(num, 2); //sqrt can be use if we increment by 2 for each multiple to account for factor pairs for (int i = 2, LIMIT2 = (int) Math.sqrt(LIMIT); i <= LIMIT2; i++) { //square numbers need to be decrement to get the right answer because an extra factor is counted int j = i * i; num[j]--; while (j <= LIMIT) { num[j] += 2; j += i; } } int count = 0; for (int i = 2; i < LIMIT + 1; i++) { if (num[i] == num[i + 1]) { count++; } } System.out.println(count);

This ran in 2.0 seconds on my computer, so my method isn’t really that slow; but IMHO, it was harder to code and harder to understand.

I have no idea how to do the rest of the problems now. It would be a miracle if I could solve another one. CU

## Leave a Reply