프로젝트 오일러 질문 3 도움

StackOverflow https://stackoverflow.com/questions/201374

문제

나는 프로젝트 Euler를 통해 일하려고 노력하고 있으며 문제 03의 장벽을 치고 있습니다. 더 작은 숫자에 맞는 알고리즘이 있지만 문제 3은 매우 많은 숫자를 사용합니다.

문제 03 :13195의 주요 요인은 5, 7, 13 및 29입니다. 숫자 600851475143의 가장 큰 주요 요인은 무엇입니까?

다음은 C#의 솔루션이 있으며 1 시간 가까이 있다고 생각합니다. 나는 실제로 이것을 직접 해결하고 싶기 때문에 답을 찾고 있지 않습니다. 주로 도움을 찾고 있습니다.

    static void Main(string[] args) {
        const long n = 600851475143;
        //const long n = 13195;
        long count, half, largestPrime = 0;
        bool IsAPrime;

        half = n / 2;

        for (long i = half; i > 1 && largestPrime == 0; i--) {
             if (n % i == 0) { // these are factors of n
                count = 1;
                IsAPrime = true;
                while (++count < i && IsAPrime) {
                    if (i % count == 0) { // does a factor of n have a factor? (not prime)
                        IsAPrime = false;
                    }
                }
                if (IsAPrime) {
                    largestPrime = i;
                }
            }
        }

        Console.WriteLine("The largest prime factor is " + largestPrime.ToString() + ".");
        Console.ReadLine();
    }
도움이 되었습니까?

해결책

우선, N / 2에서 검색을 시작하는 대신 n의 제곱근에서 시작하십시오. 당신은 요인의 절반을 얻을 수 있고 나머지 절반은 보완입니다.

예 :

n = 27
start at floor(sqrt(27)) = 5
is 5 a factor? no
is 4 a factor? no
is 3 a factor? yes. 27 / 3 = 9. 9 is also a factor.
is 2 a factor? no.
factors are 3 and 9.

다른 팁

long n = 600851475143L; //not even, so 2 wont be a factor
int factor = 3; 
while( n > 1)
{
    if(n % factor == 0)
    {
        n/=factor;
    }else
        factor += 2; //skip even numbrs
}
        print factor;

이것은 충분히 빠르야합니다 ... 통지, Prime을 확인할 필요가 없습니다 ...

실제로이 경우 원시를 확인할 필요가 없으며 찾은 요인 만 제거하십시오. n == 2로 시작하고 위쪽으로 스캔하십시오. Evil-Big-Number % n == 0 일 때, 악의-수를 n으로 나누고 작은 이벤 햄버를 계속하십시오. n> = sqrt (big-evil-number)를 중지하십시오.

현대 기계에서 몇 초 이상 걸리지 않아야합니다.

질문이 요청하지만 가장 큰 주요 요인, 반드시 먼저 그것을 찾아야한다는 의미는 아닙니다 ...

당신이하고있는 점검량을 줄여야합니다 ... 테스트해야 할 숫자에 대해 생각해보십시오.

더 나은 접근 방식을 위해 Erathosthenes의 체 ... 올바른 방향을 가리 킵니다.

NICF의 답변을 받아 들인 이유는 다음과 같습니다.

Euler의 문제는 괜찮지 만 일반적인 경우에는 효율적인 솔루션을 만들지는 않습니다. 왜 요인에 대해 짝수를 시도 하시겠습니까?

  • n이 짝수 인 경우 더 이상 없을 때까지 좌회전 (2로 나누기)을 이동하십시오. 하나라면 2가 가장 큰 주요 요인입니다.
  • N이조차도 안되면 짝수를 테스트 할 필요가 없습니다.
  • sqrt (n)에서 멈출 수 있다는 것은 사실입니다.
  • 요인에 대한 프라임 만 테스트하면됩니다. K가 n을 나누는 지 테스트 한 다음 원시를 테스트하는 것이 더 빠를 수 있습니다.
  • 요인을 찾으면 즉시 상한을 최적화 할 수 있습니다.

이것은 다음과 같은 코드로 이어질 것입니다.

n = abs(number);
result = 1;
if (n mod 2 = 0) {
  result = 2;
  while (n mod 2 = 0) n /= 2;
}
for(i=3; i<sqrt(n); i+=2) {
  if (n mod i = 0) {
    result = i;
    while (n mod i = 0)  n /= i;
  }
}
return max(n,result)

모든 요소 2와 3이 제거 된 경우 N을 6로 나눈 적이 없기 때문에 초강화 된 몇 가지 모듈로 테스트가 있습니다. 당신은 i에 대한 프라임 만 허용 할 수 있습니다.

예를 들어 21의 결과를 살펴 보겠습니다.

21은조차도 아니기 때문에 상한 SQRT (21) (~ 4.6)로 FOR 루프로 들어갑니다. 그런 다음 21을 3으로 나눌 수 있으므로 결과 = 3 및 n = 21/3 = 7입니다. 이제 우리는 SQRT (7)까지까지 테스트하면됩니다. 3보다 작기 때문에 우리는 for 루프로 끝납니다. 우리는 n의 최대 n과 결과, 즉 n = 7을 반환합니다.

내가 한 방식은 프라임을 찾는 것이 었습니다.p), Eratosthenes의 체를 사용하여 2에서 시작합니다. 이 알고리즘은 괜찮은 빠른 기계에서 <2s에서 천만 미만의 모든 프라임을 찾을 수 있습니다.

당신이 찾은 모든 프라임에 대해, 테스트는 더 이상 정수 부서를 할 수 없을 때까지 테스트하는 숫자로 나눕니다. (예 : 점검 n % p == 0 그리고 사실이라면, 나누기.)

한 번 n = 1, 당신은 끝났습니다. 마지막 값 n 성공적으로 분열 된 것은 당신의 대답입니다. 사이드 노트에서, 당신은 또한 모든 주요 요인을 찾았습니다. n 도중에.

추신 : 이전에 언급했듯이, 당신은 사이의 프라임 만 검색하면됩니다. 2 <= n <= sqrt(p). 이것은 Eratosthenes의 체를 우리의 목적을 위해 알고리즘을 매우 빠르고 쉽게 구현할 수있게합니다.

답을 찾으면 브라우저에 다음을 입력하십시오.)

http://www.wolframalpha.com/input/?i=factorinteger(600851475143)

Wofram Alpha는 당신의 친구입니다

Java에서 재귀 알고리즘을 사용하는 것은 1 초 미만으로 실행됩니다. 제거 할 수있는 "Brute-Forcing"이 포함되어 있으므로 알고리즘을 조금씩 생각해보십시오. 또한 중간 계산으로 솔루션 공간을 어떻게 줄일 수 있는지 살펴보십시오.

C ++의 쉬운 농장

#include <iostream>

using namespace std;


int main()
{
    unsigned long long int largefactor = 600851475143;
    for(int i = 2;;)
    {
        if (largefactor <= i)
            break;
        if (largefactor % i == 0)
        {
            largefactor = largefactor / i;
        }
        else
            i++;
    }

    cout << largefactor << endl;

    cin.get();
    return 0;
}

C ++ 의이 솔루션은 인텔 쿼드 코어 i5 IMAC (3.1GHz)에서 3.7ms를 차지했습니다.

#include <iostream>
#include <cmath>
#include <ctime>

using std::sqrt; using std::cin;
using std::cout; using std::endl;

long lpf(long n)
{
  long start = (sqrt(n) + 2 % 2);
  if(start % 2 == 0) start++;

  for(long i = start; i != 2; i -= 2)
    {
      if(n % i == 0) //then i is a factor of n                                                
        {
          long j = 2L;
          do {
              ++j;
             }
          while(i % j != 0 && j <= i);

          if(j == i) //then i is a prime number                                           
            return i;
        }
    }
}

int main()
{
  long n, ans;
  cout << "Please enter your number: ";
  cin >> n; //600851475143L                                                               

  time_t start, end;
  time(&start);
  int i;
  for(i = 0; i != 3000; ++i)
      ans = lpf(n);
  time(&end);

  cout << "The largest prime factor of your number is: " << ans << endl;
  cout << "Running time: " << 1000*difftime(end, start)/i << " ms." << endl;

  return 0;
}

모든 프로젝트 Euler의 문제는 1 분 이내에 걸립니다. 파이썬에서 최적화되지 않은 재귀 구현조차도 1 초 미만 [0.09 초 (CPU 4.3GHz)].

from math import sqrt

def largest_primefactor(number):
    for divisor in range(2, int(sqrt(number) + 1.5)): # divisor <= sqrt(n)
        q, r = divmod(number, divisor)
        if r == 0:
            #assert(isprime(divisor))
            # recursion depth == number of prime factors,
            # e.g. 4 has two prime factors: {2,2}
            return largest_primefactor(q) 

    return number # number is a prime itself

이것을보고 싶을 수도 있습니다.X가 프라임인지 판단 할 수 있고 단순한 필사자 프로그래머를 혼동하지 않는 간단한 알고리즘이 있습니까?

그리고 나는 Lill Mud의 해결책을 좋아합니다.

"mathn.rb"필요
600851475143.prime_division.last.first를 넣습니다

나는 그것을 확인했다 여기

어쩌면 그것은 부정 행위로 간주 될 수 있지만 Haskell의 한 가지 가능성은 글을 쓰는 것입니다 (레코드를 위해 직접 줄을 썼고 EulerProject 스레드를 확인하지 않았습니다). 

import Data.Numbers.Primes
last (primeFactors 600851475143)

사용해보십시오 Miller-Rabin 원시 테스트 숫자가 프라임을 테스트합니다. 그것은 상당히 속도를 높여야합니다.

또 다른 접근법은 모든 프라임을 최대 N/2까지 얻은 다음 모듈러스가 0인지 확인하는 것입니다. N 찾을수있다 여기.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top