Euler Project Help (Problem 12) - Prime Factors and the like
- by Richie_W
I hate to have to ask, but I'm pretty stuck here.
I need to test a sequence of numbers to find the first which has over 500 factors:
http://projecteuler.net/index.php?section=problems&id=12
-At first I attempted to brute force the answer (finding a number with 480 after a LONG time)
-I am now looking at determining the prime factors of a number and then use them to find all other factors.
I am currently at the stage where I can get an array of prime factors for any number I input - i.e 300 has the prime factors 2 2 3 5 5
Using this array of prime factors I need to be able to calculate the remaining factors - This is the part I am stuck on. Basically, as I understand it, I need to calculate ALL possible combinations of the numbers in the array...
i.e
2 * 2
2 * 2 * 3
2 * 2 * 3 * 5
2 * 3
2 * 3 * 3
...and so forth - But where it gets interesting is with things like...
2 * 5
2 * 3 * 5
...i.e Numbers which are not adjacent to each other in the array
I can't think of a way to code this in a generic fashion for any length array...
I need help! P.S - I am working in Java
EDIT: My brute force code - As it has been suggested brute forcing the problem will work and so there may be an error in my code :(
package euler.problem12;
public class Solution {
public static void main(String[] args) {
int next = 1;
int triangle = 0;
int maxFactors = 0;
while(true) {
triangle = triangle + next;
int factors = 1;
int max = (int) triangle / 2;
for(int i = 1; i <= max; ++i) {
if(triangle % i == 0) {
factors ++;
}
}
if(factors > maxFactors) {
maxFactors = factors;
System.out.println(triangle + "\t" + factors);
}
next++;
}
}
}
