Euler Project Help (Problem 12) - Prime Factors and the like

Posted by Richie_W on Stack Overflow See other posts from Stack Overflow or by Richie_W
Published on 2008-11-10T08:38:28Z Indexed on 2010/05/14 9:54 UTC
Read the original article Hit count: 232

Filed under:
|

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++;
        }
    }
}

© Stack Overflow or respective owner

Related posts about project-euler

Related posts about java