Skip to content
April 24, 2011 / oop123

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 (p_1^{m_1})(p_2^{m_2})(p_3^{m_3})... where p is a unique prime number. The number of factors can be found by calculating (m_1 + 1)(m_2 + 1)(m_3 + 1)... 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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: