오일러 프로젝트 도움말 (문제 12) - 프라임 팩터 등

Question

나는 물어 보는 것을 싫어하지만, 나는 여기에서 꽤 붙어있다. http://projecteuler.net/index.php?section=problems&id=12

-At 먼저 내가 (긴 시간 후 480 번호를 찾는) 답을 무력을 시도

을 :

나는 500 개 이상의 요소를 가지고있는 첫 번째를 찾기 위해 일련의 숫자를 테스트해야

저는 이제 숫자의 소수 요소를 결정한 다음 다른 요소를 찾는 데 사용하고 있습니다.

내가 어떤 번호 I 입력을위한 주요 요소의 배열을 얻을 수있는 단계에서 현재입니다 - 즉, (300)는 주요 내가 할 필요가 주요 요인이 배열을 사용하여 2 2 3 5 5

요인이있다 나머지 요인을 계산할 수 있습니다 - 이것은 내가 붙어있는 부분입니다. 나는 그것을 이해 기본적으로, 나는 ... 배열의 숫자의 모든 가능한 조합을 계산해야

즉 2 * 2
2 * 2 * 3
2 * 2 * 3 * 5
2 * 3
2 * 3 * 3
... 등등 - 그러나이 흥미로운 얻을 경우 같은 것들로는 ...
2 * 5
2 * 3 개 * 5 개
... 즉, 숫자 배열에서 서로 인접하지 않은 배열

길이 배열에 대해 일반적인 방법으로 코드를 작성하는 방법을 생각할 수 없습니다 ...

도움이 필요합니다! PS - 내가 편집 자바

에

하고 있어요 : 내 무력 코드 - 그것은 작동 그래서 지금까지 내 코드 :(

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

Answer 1

에 오류가있을 수 있습니다 문제를 강제로 짐승을 제시 한 바와 같이 내가 말할 수있는, 질문 (12)는 소수에 대해 아무것도 언급하지 않는 이유는 무엇입니까? 이것은 당신이 삼각형 숫자의 순서는 자연수를 추가하여 생성?

보고있는 한 ...

인가

그렇다면 소수에 대해 생각하지 않는 것이 도움이 될까요? ;)

Answer 2

OK, 두 번째 시도는 너무 어렵게 만들었습니다.

대답이 여기에 주어집니다 : http://mathforum.org/library/drmath/view/57151.html

당신은 그것의 주요 전원 요인에 숫자를 고려하면, 총 요소 그 결과를 하나의 모든 지수를 추가하고 를 곱하여 발견 함께. 예 : 108 = 2^2 * 3^3이므로 요소의 총 수는 (2 + 1) * (3 + 1) = 3 * 4 = 12입니다. 물론 108 요소는 1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54 및 108.이것은 하나의 요소이기 때문에 숫자가 동일한 소수를 가져야하며 같거나 낮은 수준으로 높아야하기 때문에 이런 현상이 발생합니다.

만약 당신이 소수 요소를 알고 있다면, 반복되는 것들을 세고 위의 계산을 사용하여 요인 수를 알아 내면됩니다.

Answer 3

은 아마도 3개월 너무 늦게, 그러나 여기가

난 당신이 생성 방법에 그 대답이 당신에게 필요한 해답을 제공 할 수있는 기능을 privided했다 볼 수 있지만, 원래의 질문에 대답 ...가는 모든 당신을 가정 요인은 어떤 이유로 필요하고 여기 당신이 어떻게 : 당신이 배열의 요소를 가지고 있다고 가정

을 :

INT [] primeFactors = 새로운 INT [] {2, 2, 3, 5, 5};

당신이해야 할 일은 각각의 가능한 깊이에 대한 순차적 인 모든 순열을 되풀이 한 다음 결과 집합을 고유 한 값으로 줄이는 것입니다.

내가 의미하는 바를 설명하겠다 : "순차적 순열": 배열의 위치 0에서 시작한다고 가정하면 다음 요소는 1, 2, 3 또는 4 여야한다. 다음은 2, 3 또는 4 등이어야합니다.

"가능한 한 각 깊이": 모든 단일 요소, ​​두 개의 모든 요소, 세 개의 요소 등 모든 다섯 가지 요소가 될 때까지 계속됩니다.

"세트를 감소": 당신이 두 가지 요소를 가지고가는 경우에, 0 & 3, 0 & 4, 1 4 그들은 모두 당신에게 * 5 = 10, 모두가 요소 (10)를 제공하는 2, 그래서 말 당신은 당신의 세트를 뚜렷한 가치로 끌어 올 필요가 있습니다. (휴, 이것은 내가 예상했던 것보다 길어지고있다. :) :)

이 방법은 최대 재귀 깊이를 선택하는 두 가지 방법을 사용하여 재연을 시작하고 최종 결과를 얻는 것입니다 , 다른 하나는 값을 재귀합니다 :

public static void main(String[] args) { 
    int[] primeFactors = new int[] {2, 2, 3, 5, 5}; 
    List<Integer> allFactors = getAllFactors(primeFactors); 
    for (int factor : allFactors) { 
     System.out.println("Factor: " + factor); 
    } 
} 

private static List<Integer> getAllFactors(int[] primeFactors) { 
    Set<Integer> distinctFactors = new HashSet<Integer>(); 
    for (int maxDepth = 0; maxDepth <= primeFactors.length; maxDepth++) { 
     permutatPrimeFactors(0, maxDepth, 0, 1, primeFactors, distinctFactors); 
    } 
    List<Integer> result = new ArrayList<Integer>(distinctFactors); 
    Collections.sort(result); 
    return result; 
} 

private static void permutatPrimeFactors(int depth, int maxDepth, int minIndex, int valueSoFar, int[] primeFactors, Set<Integer> distinctFactors) { 
    if (depth == maxDepth) { 
     distinctFactors.add(valueSoFar); 
     return; 
    } 

    for (int index = minIndex; index < primeFactors.length; index++) { 
     permutatPrimeFactors(depth + 1, maxDepth, index + 1, valueSoFar * primeFactors[index], primeFactors, distinctFactors); 
    } 
} 

getAllFactors 확실히 우리는 고유 한 값을 얻을 수 있도록하기 위해 설정을 사용하여, 우리는 위해 요소를 표시 할 수있는 목록과 종류에 추가보다.

permutatPrimeFactors는 모든 용어 (factor = 1 * 2 * 2 * 3 * 5 * 5 = 300)에서 0 항 (factor = 1)을 생성합니다.

희망이 있습니다.