게시판
숫자의 가장 큰 소인수를 찾는 알고리즘
losenoid531857 ・ 2022. 2. 11. 19:16
URL 복사 이웃추가
본문 기타 기능
신고하기
숫자의 가장 큰 소인수를 계산하는 가장 좋은 방법은 무엇입니까?
가장 효율적인 방법은 다음과 같습니다.
깔끔하게 나누는 가장 작은 소수 찾기
나눗셈의 결과가 소수인지 확인
그렇지 않은 경우 다음 최저값을 찾습니다.
2로 이동합니다.
나는 작은 소인수를 계산하는 것이 더 쉽다는 가정을 하고 있습니다. 이게 맞나요? 다른 어떤 접근 방식을 살펴봐야 합니까?
편집: 나는 결과가 두 개의 다른 소수의 곱일 때 2단계가 실패하므로 재귀 알고리즘이 필요하기 때문에 2개 이상의 소인수가 있는 경우 내 접근 방식이 무익하다는 것을 깨달았습니다.
다시 편집: 그리고 이제 마지막으로 발견된 소수가 가장 높은 숫자여야 하기 때문에 이것이 여전히 작동한다는 것을 깨달았습니다. 따라서 2단계에서 소수가 아닌 결과를 더 테스트하면 소수가 더 작아질 것입니다.
n보다 작은 가능한 모든 소수를 어딘가에 저장하고 가장 큰 약수를 찾기 위해 반복하는 것이 좋을 것이라고 생각합니다. Prime-numbers.org 에서 소수를 얻을 수 있습니다.
물론 나는 당신의 숫자가 너무 크지 않다고 가정합니다 :)
이것은 아마도 항상 더 빠르지는 않지만 큰 소수를 찾는 것에 대해 더 낙관적입니다.
N 은 당신의 번호입니다
소수이면 return(N)
Sqrt(N) 까지 소수 계산
소수를 내림차순으로 살펴보세요(큰 것부터).
N is divisible by Prime 지면 Return(Prime)
편집: 3단계에서 에라토스테네스의 체 또는 앳킨스의 체 또는 원하는 대로 사용할 수 있지만 그 자체로는 가장 큰 주요 요소를 찾지 못할 것입니다. (그래서 SQLMenace의 게시물을 공식 답변으로 선택하지 않을 것입니다...)
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에 대해서만 소수를 허용할 수 있습니다. 이는 여기에서 다른 몇 가지 답변에 나와 있습니다.
여기에서 에라토스테네스의 체를 실제로 엮을 수 있습니다.
먼저 정수 목록을 만듭니다.
sqrt(n) .
for 루프에서 모든 배수를 표시하십시오.
i의 새로운 sqrt(n) 까지
프라임을 사용하고 대신 while 루프를 사용하세요.
i를 다음 소수로 설정
목록.
또한 이 질문 을 참조하십시오.
실제로 큰 숫자의 요인을 찾는 몇 가지 더 효율적인 방법이 있습니다(작은 숫자의 경우 시행 분할이 합리적으로 잘 작동함).
입력 수의 제곱근에 매우 가까운 두 개의 인수가 있는 경우 매우 빠른 한 가지 방법을 페르마 인수분해( Fermat Factorization )라고 합니다. N = (a + b)(a - b) = a^2 - b^2 항등식을 사용하며 이해하고 구현하기 쉽습니다. 불행히도 일반적으로 매우 빠르지 않습니다.
최대 100자리 숫자까지 인수분해하는 가장 잘 알려진 방법은 2차 체( Quadratic sieve )입니다. 보너스로 알고리즘의 일부는 병렬 처리로 쉽게 수행됩니다.
내가 들어본 또 다른 알고리즘은 Pollard의 Rho 알고리즘 입니다. 일반적으로 Quadratic Sieve만큼 효율적이지는 않지만 구현하기가 더 쉬운 것 같습니다.
숫자를 두 개의 요인으로 나누는 방법을 결정했다면 다음은 숫자의 가장 큰 소인수를 찾기 위해 생각할 수 있는 가장 빠른 알고리즘입니다.
처음에 숫자 자체를 저장하는 우선 순위 대기열을 만듭니다. 반복할 때마다 대기열에서 가장 높은 수를 제거하고 두 요소로 분할하려고 시도합니다(물론 1이 이러한 요소 중 하나가 되는 것은 허용하지 않음). 이 단계가 실패하면 숫자가 소수이고 답이 있습니다! 그렇지 않으면 대기열에 두 가지 요소를 추가하고 반복합니다.
가장 간단한 솔루션은 상호 재귀 함수 쌍입니다.
첫 번째 함수는 모든 소수를 생성합니다.
1보다 큰 모든 자연수의 목록으로 시작하십시오.
소수가 아닌 모든 숫자를 제거하십시오. 즉, 소인수(자신 외에)가 없는 숫자입니다. 아래를 참조하십시오.
두 번째 함수는 주어진 숫자 n 의 소인수를 오름차순으로 반환합니다.
모든 소수의 목록을 가져옵니다(위 참조).
n 의 인수가 아닌 모든 숫자를 제거합니다.
n 의 가장 큰 소인수는 두 번째 함수에 의해 주어진 마지막 숫자입니다.
이 알고리즘에는 지연 목록 또는 필요에 따른 호출 의미 체계가 있는 언어(또는 데이터 구조)가 필요합니다.
설명을 위해 다음은 Haskell에서 위의 (비효율적인) 구현 중 하나입니다.
import Control.Monad-- All the primesprimes = 2 : filter (ap (<=) (head . primeFactors)) [3,5..]-- Gives the prime factors of its argumentprimeFactors = factor primes where factor [] n = [] factor xs@(p:ps) n = if p*p > n then [n] else let (d,r) = divMod n p in if r == 0 then p : factor xs d else factor ps n-- Gives the largest prime factor of its argumentlargestFactor = last . primeFactors
이것을 더 빠르게 만드는 것은 어떤 숫자가 소수 및/또는 n 의 인수인지 감지하는 데 더 영리한 문제일 뿐이지만 알고리즘은 동일하게 유지됩니다.
모든 숫자는 소수의 곱으로 표현할 수 있습니다. 예:
102 = 2 x 3 x 17712 = 2 x 2 x 2 x 89
단순히 2에서 시작하여 결과가 숫자의 배수가 아닐 때까지 계속 나누면 이러한 값을 찾을 수 있습니다.
712 / 2 = 356 .. 356 / 2 = 178 .. 178 / 2 = 89 .. 89 / 89 = 1
이 방법을 사용하면 실제로 소수를 계산할 필요가 없습니다. 이전의 모든 숫자로 가능한 한 많이 숫자를 이미 인수분해했다는 사실에 따라 모두 소수가 됩니다.
number = 712;currNum = number; // the value we'll actually be working withfor (currFactor in 2 .. number) { while (currNum % currFactor == 0) { // keep on dividing by this number until we can divide no more! currNum = currNum / currFactor // reduce the currNum } if (currNum == 1) return currFactor; // once it hits 1, we're done.}
주어진 알고리즘의 2단계는 그다지 효율적인 접근 방식이 아닌 것 같습니다. 당신은 그것이 프라임이라는 합리적인 기대가 없습니다.
또한 에라토스테네스의 체를 제안하는 이전 답변은 완전히 잘못된 것입니다. 방금 인수 123456789에 두 개의 프로그램을 작성했습니다. 하나는 Sieve를 기반으로 하고 하나는 다음을 기반으로 합니다.
1) Test = 2 2) Current = Number to test 3) If Current Mod Test = 0 then 3a) Current = Current Div Test 3b) Largest = Test3c) Goto 3. 4) Inc(Test) 5) If Current < Test goto 46) Return Largest
이 버전은 Sieve보다 90배 빠릅니다.
문제는 최신 프로세서에서 작업 유형이 작업 수보다 훨씬 덜 중요하다는 것입니다. 위의 알고리즘은 캐시에서 실행할 수 있지만 Sieve는 실행할 수 없습니다. Sieve는 모든 합성 숫자를 제거하는 많은 연산을 사용합니다.
또한 식별된 대로 요소를 나누면 테스트해야 하는 공간이 줄어듭니다.
내가 아는 최고의 알고리즘은 다음과 같습니다(Python에서).
def prime_factors(n): """Returns all the prime factors of a positive integer""" factors = [] d = 2 while n > 1: while n % d == 0: factors.append(d) n /= d d = d + 1 return factorspfs = prime_factors(1000)largest_prime_factor = max(pfs) # The largest element in the prime factor list
위의 방법은 최악의 경우(입력이 소수인 경우 O(n) 에서 실행됩니다.
편집하다:
아래는 주석에서 제안한 대로 O(sqrt(n)) 버전입니다. 여기 코드가 있습니다. 다시 한 번.
def prime_factors(n): """Returns all the prime factors of a positive integer""" factors = [] d = 2 while n > 1: while n % d == 0: factors.append(d) n /= d d = d + 1 if d*d > n: if n > 1: factors.append(n) break return factorspfs = prime_factors(1000)largest_prime_factor = max(pfs) # The largest element in the prime factor list
내 대답은 Triptych 를 기반으로 하지만 많이 개선되었습니다. 2와 3을 넘어서는 모든 소수는 6n-1 또는 6n+1 형식이라는 사실에 근거합니다.
var largestPrimeFactor;if(n mod 2 == 0){ largestPrimeFactor = 2; n = n / 2 while(n mod 2 == 0);}if(n mod 3 == 0){ largestPrimeFactor = 3; n = n / 3 while(n mod 3 == 0);}multOfSix = 6;while(multOfSix - 1 <= n){ if(n mod (multOfSix - 1) == 0) { largestPrimeFactor = multOfSix - 1; n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0); } if(n mod (multOfSix + 1) == 0) { largestPrimeFactor = multOfSix + 1; n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0); } multOfSix += 6;}
나는 최근에 이 알고리즘이 어떻게 작동하는지 설명하는 블로그 기사 를 작성했습니다.
나는 소수에 대한 테스트가 필요하지 않은(그리고 체 구성이 없는) 방법이 그것을 사용하는 방법보다 더 빨리 실행될 것이라고 감히 생각합니다. 만약 그렇다면, 이것은 아마도 여기에서 가장 빠른 알고리즘일 것입니다.
#include<stdio.h>#include<conio.h>#include<math.h>#include <time.h>factor(long int n){long int i,j;while(n>=4) {if(n%2==0) { n=n/2; i=2; } else { i=3;j=0; while(j==0) { if(n%i==0) {j=1; n=n/i; } i=i+2; } i-=2; } }return i; } void main() { clock_t start = clock(); long int n,sp; clrscr(); printf("enter value of n"); scanf("%ld",&n); sp=factor(n); printf("largest prime factor is %ld",sp); printf("Time elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC); getch(); }
나는 이것이 빠른 해결책이 아니라는 것을 알고 있습니다. 느린 솔루션을 이해하기 쉽게 게시합니다.
public static long largestPrimeFactor(long n) { // largest composite factor must be smaller than sqrt long sqrt = (long)Math.ceil(Math.sqrt((double)n)); long largest = -1; for(long i = 2; i <= sqrt; i++) { if(n % i == 0) { long test = largestPrimeFactor(n/i); if(test > largest) { largest = test; } } } if(largest != -1) { return largest; } // number is prime return n; }
다음은 약간 단순화된 생성기로 제공되는 동일한 function@Triptych입니다.
def primes(n): d = 2 while (n > 1): while (n%d==0): yield d n /= d d += 1
최대 소수는 다음을 사용하여 찾을 수 있습니다.
n= 373764623max(primes(n))
다음을 사용하여 찾은 요인 목록:
list(primes(n))
먼저 소수를 저장하는 목록을 계산하십시오(예: 2 3 5 7 11 13 ...
숫자를 소인수분해할 때마다 Triptych에 의한 구현을 사용하되 자연 정수보다는 이 소수 목록을 반복하십시오.
다음은 C#에서의 시도입니다. 마지막 출력물은 숫자의 가장 큰 소인수입니다. 나는 확인했고 작동합니다.
namespace Problem_Prime{ class Program { static void Main(string[] args) { /* The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? */ long x = 600851475143; long y = 2; while (y < x) { if (x % y == 0) { // y is a factor of x, but is it prime if (IsPrime(y)) { Console.WriteLine(y); } x /= y; } y++; } Console.WriteLine(y); Console.ReadLine(); } static bool IsPrime(long number) { //check for evenness if (number % 2 == 0) { if (number == 2) { return true; } return false; } //don't need to check past the square root long max = (long)Math.Sqrt(number); for (int i = 3; i <= max; i += 2) { if ((number % i) == 0) { return false; } } return true; } }}
자바:
int 값의 경우:
public static int[] primeFactors(int value) { int[] a = new int[31]; int i = 0, j; int num = value; while (num % 2 == 0) { a[i++] = 2; num /= 2; } j = 3; while (j <= Math.sqrt(num) + 1) { if (num % j == 0) { a[i++] = j; num /= j; } else { j += 2; } } if (num > 1) { a[i++] = num; } int[] b = Arrays.copyOf(a, i); return b;}
long 값의 경우:
static long[] getFactors(long value) { long[] a = new long[63]; int i = 0; long num = value; while (num % 2 == 0) { a[i++] = 2; num /= 2; } long j = 3; while (j <= Math.sqrt(num) + 1) { if (num % j == 0) { a[i++] = j; num /= j; } else { j += 2; } } if (num > 1) { a[i++] = num; } long[] b = Arrays.copyOf(a, i); return b;}
//this method skips unnecessary trial divisions and makes //trial division more feasible for finding large primes public static void main(String[] args) { long n= 1000000000039L; //this is a large prime number long i = 2L; int test = 0; while (n > 1) { while (n % i == 0) { n /= i; } i++; if(i*i > n && n > 1) { System.out.println(n); //prints n if it's prime test = 1; break; } } if (test == 0) System.out.println(i-1); //prints n if it's the largest prime factor }
#python implementationimport mathn = 600851475143i = 2factors=set([])while i<math.sqrt(n): while n%i==0: n=n/i factors.add(i) i+=1factors.add(n)largest=max(factors)print factorsprint largest
C++에서 재귀를 사용하여 숫자의 가장 큰 소인수를 계산합니다. 코드 작업은 아래에 설명되어 있습니다.
int getLargestPrime(int number) { int factor = number; // assumes that the largest prime factor is the number itself for (int i = 2; (i*i) <= number; i++) { // iterates to the square root of the number till it finds the first(smallest) factor if (number % i == 0) { // checks if the current number(i) is a factor factor = max(i, number / i); // stores the larger number among the factors break; // breaks the loop on when a factor is found } } if (factor == number) // base case of recursion return number; return getLargestPrime(factor); // recursively calls itself}
숫자에서 모든 소인수를 제거하는 Python 반복적 접근
def primef(n): if n <= 3: return n if n % 2 == 0: return primef(n/2) elif n % 3 ==0: return primef(n/3) else: for i in range(5, int((n)**0.5) + 1, 6): #print i if n % i == 0: return primef(n/i) if n % (i + 2) == 0: return primef(n/(i+2)) return n
다음은 가장 큰 소인수를 빠르게 계산하는 방법입니다.
수정된 x 는 소인수가 아닌 요소를 포함하지 않는다는 사실에 기반합니다. 이를 달성하기 위해 요인이 발견되는 즉시 x 를 나눕니다. 그런 다음 남은 것은 가장 큰 인수를 반환하는 것뿐입니다. 이미 전성기일 것입니다.
코드(하스켈):
f max' x i | i > x = max' | x `rem` i == 0 = f i (x `div` i) i -- Divide x by its factor | otherwise = f max' x (i + 1) -- Check for the next possible factorg x = f 2 x 2
자바스크립트 코드:
'option strict';function largestPrimeFactor(val, divisor = 2) { let square = (val) => Math.pow(val, 2); while ((val % divisor) != 0 && square(divisor) <= val) { divisor++; } return square(divisor) <= val ? largestPrimeFactor(val / divisor, divisor) : val;}
사용 예:
let result = largestPrimeFactor(600851475143);
다음은 코드의 예입니다 .
다음 C++ 알고리즘은 최고의 알고리즘은 아니지만 10억 미만의 숫자에 대해 작동하며 매우 빠릅니다.
#include <iostream>using namespace std;// ------ is_prime ------// Determines if the integer accepted is prime or notbool is_prime(int n){ int i,count=0; if(n==1 || n==2) return true; if(n%2==0) return false; for(i=1;i<=n;i++){ if(n%i==0) count++; } if(count==2) return true; else return false; } // ------ nextPrime ------- // Finds and returns the next prime number int nextPrime(int prime){ bool a = false; while (a == false){ prime++; if (is_prime(prime)) a = true; } return prime; } // ----- M A I N ------ int main(){ int value = 13195; int prime = 2; bool done = false; while (done == false){ if (value%prime == 0){ value = value/prime; if (is_prime(value)){ done = true; } } else { prime = nextPrime(prime); } } cout << "Largest prime factor: " << value << endl; }
숫자를 현재 프라임 팩터로 계속 나누는 알고리즘을 사용하고 있습니다.
파이썬 3의 내 솔루션 :
def PrimeFactor(n): m = n while n%2==0: n = n//2 if n == 1: # check if only 2 is largest Prime Factor return 2 i = 3 sqrt = int(m**(0.5)) # loop till square root of number last = 0 # to store last prime Factor i.e. Largest Prime Factor while i <= sqrt : while n%i == 0: n = n//i # reduce the number by dividing it by it's Prime Factor last = i i+=2 if n> last: # the remaining number(n) is also Factor of number return n else: return lastprint(PrimeFactor(int(input())))
입력 : 10
출력 : 5
입력 : 600851475143
출력 : 6857
@Triptych 답변과 유사하지만 다릅니다. 이 예제에서는 목록이나 사전이 사용되지 않습니다. 코드는 Ruby로 작성되었습니다.
def largest_prime_factor(number) i = 2 while number > 1 if number % i == 0 number /= i; else i += 1 end end return iendlargest_prime_factor(600851475143)# => 6857
"James Wang"이 웹에서 이 솔루션을 찾았습니다.
public static int getLargestPrime( int number) { if (number <= 1) return -1; for (int i = number - 1; i > 1; i--) { if (number % i == 0) { number = i; } } return number;}
체를 사용한 소인수:
#include <bits/stdc++.h>using namespace std;#define N 10001 typedef long long ll;bool visit[N];vector<int> prime;void sieve(){ memset( visit , 0 , sizeof(visit)); for( int i=2;i<N;i++ ) { if( visit[i] == 0) { prime.push_back(i); for( int j=i*2; j<N; j=j+i ) { visit[j] = 1; } } } }void sol(long long n, vector<int>&prime){ ll ans = n; for(int i=0; i<prime.size() || prime[i]>n; i++) { while(n%prime[i]==0) { n=n/prime[i]; ans = prime[i]; } } ans = max(ans, n); cout<<ans<<endl;}int main() { ll tc, n; sieve(); cin>>n; sol(n, prime); return 0;}
다음은 Clojure에서 시도한 내용입니다. prime? 및 소인수에 대한 소수 즉. sieve . 지연 시퀀스를 사용하면 값이 필요하기 직전에 값을 생성하는 데 도움이 됩니다.
(defn prime? ([n] (let [oddNums (iterate #(+ % 2) 3)] (prime? n (cons 2 oddNums)))) ([n [i & is]] (let [q (quot n i) r (mod n i)] (cond (< n 2) false (zero? r) false (> (* i i) n) true :else (recur n is)))))(def primes (let [oddNums (iterate #(+ % 2) 3)] (lazy-seq (cons 2 (filter prime? oddNums)))));; Sieve of Eratosthenes(defn sieve ([n] (sieve primes n)) ([[i & is :as ps] n] (let [q (quot n i) r (mod n i)] (cond (< n 2) nil (zero? r) (lazy-seq (cons i (sieve ps q))) (> (* i i) n) (when (> n 1) (lazy-seq [n])) :else (recur is n)))))(defn max-prime-factor [n] (last (sieve n)))
추측해, 위의 예에서 수행한 것처럼 인수분해를 수행하는 것 외에는 즉각적인 방법이 없습니다.
반복에서 숫자 N 의 "작은" 인자 f 를 식별한 다음 축소된 문제 "인자 후보 >=f 로 N':=N/f 의 가장 큰 소인수 찾기"로 계속 진행합니다.
f 의 특정 크기에서 예상 검색 시간이 더 적습니다. 감소된 N' 에 대해 소수 테스트를 수행하면 N' 이 이미 초기 N 의 가장 큰 소인수임을 확인할 수 있습니다.
귀하의 질문에 영감을 받아 저는 Python에서 자체 버전의 인수분해(및 가장 큰 소인수 찾기)를 구현하기로 결정했습니다.
내가 알고 있는 구현하기 가장 간단하지만 매우 효율적인 인수분해 알고리즘은 아마도 Pollard의 Rho 알고리즘일 것입니다. 시분할 알고리즘의 실행 시간은 최대 O(N^(1/4)) 로 O(N^(1/2)) 보다 훨씬 빠릅니다. 두 알고리즘 모두 합성(소수가 아닌) 숫자의 경우에만 이러한 실행 시간을 갖기 때문에 소수(인수 분해할 수 없는) 숫자를 필터링하는 데 소수 테스트를 사용해야 합니다.
내 코드에서 다음 알고리즘을 사용했습니다: Fermat Primality Test ..., Pollard's Rho Algorithm ..., Trial Division Algorithm . 페르마 소수성 테스트는 소수를 필터링하기 위해 Pollard의 Rho를 실행하기 전에 사용됩니다. 매우 드문 경우에 Pollard의 Rho가 특히 일부 소수의 경우 요인을 찾지 못할 수 있기 때문에 Trial Division이 대체 수단으로 사용됩니다.
분명히 숫자를 정렬된 소인수 목록으로 완전히 분해한 후 가장 큰 소인수가 이 목록의 마지막 요소가 됩니다. 일반적으로 (임의의 숫자에 대해) 나는 숫자를 완전히 인수분해하는 것 외에 가장 큰 소인수를 찾는 다른 방법을 모릅니다.
내 코드의 예로서 Pi의 처음 190 개 소수 자릿수를 인수분해하고 코드는 1초 이내에 이 숫자를 인수분해하며 크기가 165 자리(545비트)인 가장 큰 소인수를 보여줍니다!
온라인으로 사용해 보세요!
def is_fermat_probable_prime(n, *, trials = 32): # https://en.wikipedia.org/wiki/Fermat_primality_test import random if n <= 16: return n in (2, 3, 5, 7, 11, 13) for i in range(trials): if pow(random.randint(2, n - 2), n - 1, n) != 1: return False return Truedef pollard_rho_factor(N, *, trials = 16): # https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm import random, math for j in range(trials): i, stage, y, x = 0, 2, 1, random.randint(1, N - 2) while True: r = math.gcd(N, x - y) if r != 1: break if i == stage: y = x stage <<= 1 x = (x * x + 1) % N i += 1 if r != N: return [r, N // r] return [N] # Pollard-Rho faileddef trial_division_factor(n, *, limit = None): # https://en.wikipedia.org/wiki/Trial_division fs = [] while n & 1 == 0: fs.append(2) n >>= 1 d = 3 while d * d <= n and limit is None or d <= limit: q, r = divmod(n, d) if r == 0: fs.append(d) n = q else: d += 2 if n > 1: fs.append(n) return fsdef factor(n): if n <= 1: return [] if is_fermat_probable_prime(n): return [n] fs = trial_division_factor(n, limit = 1 << 12) if len(fs) >= 2: return sorted(fs[:-1] + factor(fs[-1])) fs = pollard_rho_factor(n) if len(fs) >= 2: return sorted([e1 for e0 in fs for e1 in factor(e0)]) return trial_division_factor(n)def demo(): import time, math # http://www.math.com/tables/constants/pi.htm # pi = 3. # 1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679 # 8214808651 3282306647 0938446095 5058223172 5359408128 4811174502 8410270193 8521105559 6446229489 5493038196 # n = first 190 fractional digits of Pi n = 1415926535_8979323846_2643383279_5028841971_6939937510_5820974944_5923078164_0628620899_8628034825_3421170679_8214808651_3282306647_0938446095_5058223172_5359408128_4811174502_8410270193_8521105559_6446229489 print('Number:', n) tb = time.time() fs = factor(n) print('All Prime Factors:', fs) print('Largest Prime Factor:', f'({math.log2(fs[-1]):.02f} bits, {len(str(fs[-1]))} digits)', fs[-1]) print('Time Elapsed:', round(time.time() - tb, 3), 'sec')if __name__ == '__main__': demo()
산출:
Number: 1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489All Prime Factors: [3, 71, 1063541, 153422959, 332958319, 122356390229851897378935483485536580757336676443481705501726535578690975860555141829117483263572548187951860901335596150415443615382488933330968669408906073630300473]Largest Prime Factor: (545.09 bits, 165 digits) 122356390229851897378935483485536580757336676443481705501726535578690975860555141829117483263572548187951860901335596150415443615382488933330968669408906073630300473Time Elapsed: 0.593 sec
댓글쓰기 이 글에 댓글 단 블로거 열고 닫기
인쇄
