소수 번호 문제

Question

매우 큰 소수의 가장 큰 소수 요소를 찾기 위해 프로그램을 작성하려고 시도하고 다양한 성공으로 여러 가지 방법을 시도했습니다. 지금까지 내가 발견 한 모든 것들은 믿을 수 없을 정도로 느리다. 나는 생각했다, 이것은 유효한 방법 인 경우 궁금 :이 방법은 입력 걸릴 것

long number = input; 

while(notPrime(number)) 
{ 
    number = number/getLowestDivisiblePrimeNumber(); 
} 

return number; 

, 다음 할 것 :

200 -> 100 -> 50 -> 25 - > 5 (창)

90 -> 45 -> 15 -> 5 (창)

그것은 (대부분 2, 3) 최소 나눌 번호 반복 currentNum 분할 currentNum 자체가 소수 일 때까지 (이 currentNum의 squareroot보다 작은 분할 가능 소수 (prime number)가 없다.), 이것을 larg라고 가정한다. 원본 입력의 추정 소수 요소.

항상 작동합니까? 그렇지 않다면 누군가가 반례를 줄 수 있습니까?

-

편집 : 매우 큰, 나는 약^40 (2), 또는^11 (10)를 의미한다.

Answer 1

Unique Prime Factorization Theorem 때문에 항상 작동합니다.

Answer 2

숫자의 prime factors을 찾으려고합니다. 당신이 제안하는 것은 효과가있을 것이지만 여전히 큰 숫자에 대해서는 느릴 것입니다. 왜냐하면 현대적인 보안은 이것이 어려운 문제라는 전제하에 있기 때문에 당신은 이것에 대해 감사해야합니다.

Answer 3

확실히 작동 할 것이지만 (Mark Byers' answer 참조) "매우 큰"입력의 경우 너무 오래 걸릴 수 있습니다. getLowestDivisiblePrimeNumber()에 대한 호출이 다른 루프를 숨기므로 O (N^2)에서 실행되며 "매우 큰"의미에 따라 BigNums에서 작동해야하는 속도가 느려질 수 있습니다.

알고리즘은 마지막으로 발견 된 것보다 작은 요소를 확인하지 않아도된다는 것을 지적함으로써 약간 속도를 높일 수 있습니다.

Answer 4

이 방법은 효과가 있지만 느립니다. "당신 번호가 얼마나 큽니까?" 사용 방법을 결정합니다.

• 2^16 이하 : 조회 표.
• 2^70 이하 : Sieve of Atkin. 이것은 잘 알려진 Sieve of Eratosthenes의 최적화 된 버전입니다. 편집 :Richard Brent's modification이 Pollard's rho algorithm 인 경우 더 좋을 수 있습니다.
• 미만 10^50 : Lenstra elliptic curve factorization
• 미만 10^100 : Quadratic Sieve
• 이상 10^100 : 그냥 한 빠른 검색에서 General Number Field Sieve

Answer 5

, 가장 빠른 알려진 방법은 요인 숫자는 Elliptic Curve Method를 사용하는 것입니다.

이 데모에서 번호를 던집니다. http://www.alpertron.com.ar/ECM.HTM.

당신이 확신한다면, 코드를 훔쳐서 (재미 있지도 않고, 링크를 제공합니다!) 또는 다른 곳에서 이론을 읽으려고 시도 할 수 있습니다. 여기 그것에 대한 위키피디아 문서가 있습니다 : http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization하지만 나는 그것을 이해하기에는 너무 바보입니다. 고맙게도, 그건 내 문제가 아니야! :)

Answer 6

프로젝트 오일러의 문제는 대개 영원히 걸릴 문제를 수행하는 명백한 brute-force 방법이 있다는 것입니다. 질문이 어려워 질수록 똑똑한 솔루션을 구현해야합니다.

이 문제를 해결할 수있는 한 가지 방법은 항상 숫자의 최소 (양의 정수) 요소를 찾는 루프를 사용하는 것입니다. 숫자의 가장 작은 요소가 그 숫자라면 가장 큰 소수 요소를 찾았습니다!

자세한 알고리즘 설명 :

당신은 세 가지 변수를 유지하여이 작업을 수행 할 수 있습니다 :

당신이 인수 분해하려고하는 수 (A) 현재 제수 저장소 (B) 가장 큰 약수 점 (C)

처음에는 관심이있는 숫자를 -이 경우는 600851475143이라고합시다. 그러면 (B)를 2로합시다. (A)가 (B)로 나눌 수 있는지 확인하는 조건이 있습니다. . 분할 할 수 있다면 (A)를 (B)로 나누고, (B)를 2로 재설정하고 (A)가 (B)로 나눌 수 있는지 확인합니다. 그렇지 않으면 (A)가 (B)로 나눌 수 없다면, (B)를 +1만큼 증가시킨 다음 (A)가 (B)로 나눌 수 있는지 확인하십시오. (A)가 1이 될 때까지 루프를 실행하십시오. (3)은 600851475143의 가장 큰 소수가 될 것입니다.

다음 정수로 증가하는 대신 여러 가지 방법으로 효과를 높일 수 있습니다. 다음 필수 정수로 증가하고, 가장 큰 약수를 유지하는 대신, 유일한 제수가 자체 일 때 현재 숫자를 반환 할 수 있습니다. 그러나 위에서 설명한 알고리즘은 아무런 문제없이 초 단위로 실행됩니다. 다음과 같이 파이썬

구현은 다음과 같습니다 -

def lpf(x): 
     lpf = 2; 
     while (x > lpf): 
       if (x%lpf==0): 
         x = x/lpf 
         lpf = 2 
       else: 
         lpf+=1; 
     print("Largest Prime Factor: %d" % (lpf)); 

def main(): 
     x = long(raw_input("Input long int:")) 
     lpf(x); 
     return 0; 

if __name__ == '__main__': 
    main() 

예 :의 위에서 설명한 방법을 사용하여 105의 가장 큰 소인수를 찾아 보자.

(A) = 105. (B) = 2 (항상 2로 시작), 아직 (C)에 대한 값이 없습니다.

(A)는 (B)로 나눌 수 있습니까? +1 증가분 (B) : (B) = 3. Is (A)가 (B)로 나눌 수 있습니까? 예. (105/3 = 35). 업데이트 (A) = 35. 재설정 (B) = 2

이제 (A)를 (B)로 나눌 수 있습니까? +1 증가분 (B) : (B) = 3. (A)가 (B)로 나눌 수 있습니까? +1 증가분 (B) : (B) = 4. (A)가 (B)로 나눌 수 있습니까? +1 증가분 (B) : (B) = 5. (A)가 (B)로 나눌 수 있습니까? 예. (35/5 = 7). 이전에 발견 한 가장 큰 약수는 (C)에 저장됩니다. (C)는 현재 3입니다. 5는 3보다 큽니다. 따라서 (C) = 5를 업데이트합니다. (A) = 7을 업데이트합니다. (B) = 2로 재설정합니다.

우리는 (A)에 대한 과정을 반복하되, 7이 소수이고 자신과 1 이외의 제수가 없으므로 (B) = (A)까지 계속 증가시킬 것입니다. (우리는 이미 숫자의 절반보다 큰 정수를 가질 수 없으므로 (B)> ((A)/2) 일 때 중단하십시오. 숫자의 최소 제수 (1이 아닌 숫자)는 2입니다!)

그래서 우리가 돌려주는 지점 (A) = 7.

손으로 다음의 몇 가지 일을 시도하고 당신이 생각 나는 당신의 마법`notPrime() '함수의 구현을보고 싶습니다