숫자의 가장 큰 소인수를 찾는 알고리즘
https://stackoverflow.com/questions/23287
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
숫자의 가장 큰 소인수를 계산하는 가장 좋은 방법은 무엇입니까?
나는 다음이 가장 효율적이라고 생각합니다.
- 깨끗하게 나누어지는 가장 낮은 소수 찾기
- 나눗셈 결과가 소수인지 확인
- 그렇지 않다면 다음으로 낮은 것을 찾는다
- 2로 가세요.
나는 작은 소인수를 계산하는 것이 더 쉽다는 가정을 바탕으로 하고 있습니다.이 정도가 맞나요?어떤 다른 접근 방식을 조사해야 합니까?
편집하다:결과가 다른 두 소수의 곱일 때 2단계가 실패하므로 재귀 알고리즘이 필요하기 때문에 2개 이상의 소인수가 작용하는 경우 내 접근 방식이 쓸모가 없다는 것을 이제 깨달았습니다.
다시 편집하세요:이제 나는 이것이 여전히 작동한다는 것을 깨달았습니다. 왜냐하면 마지막으로 발견된 소수는 가장 높은 소수여야 하기 때문입니다. 따라서 2단계에서 소수가 아닌 결과를 추가로 테스트하면 더 작은 소수가 생성됩니다.
해결책
실제로 큰 숫자의 인수를 찾는 더 효율적인 방법이 여러 가지 있습니다(작은 인수의 경우 시험 분할이 합리적으로 잘 작동함).
입력 숫자의 제곱근에 매우 가까운 두 가지 요소가 있는 경우 매우 빠른 방법 중 하나는 다음과 같습니다. 페르마 인수분해.이는 N = (a + b)(a - b) = a^2 - b^2 항등식을 사용하며 이해하고 구현하기 쉽습니다.불행히도 일반적으로 매우 빠르지는 않습니다.
최대 100자리의 숫자를 인수분해하는 가장 잘 알려진 방법은 다음과 같습니다. 이차 체.보너스로, 알고리즘의 일부는 병렬 처리를 통해 쉽게 수행됩니다.
내가 들어본 또 다른 알고리즘은 다음과 같습니다. 폴라드의 Rho 알고리즘.일반적으로 Quadratic Sieve만큼 효율적이지는 않지만 구현하기가 더 쉬운 것 같습니다.
숫자를 두 개의 요소로 분할하는 방법을 결정한 후 숫자의 가장 큰 소인수를 찾기 위해 제가 생각할 수 있는 가장 빠른 알고리즘은 다음과 같습니다.
처음에 번호 자체를 저장하는 우선순위 대기열을 만듭니다.각 반복마다 대기열에서 가장 높은 숫자를 제거하고 이를 두 개의 요소로 분할하려고 시도합니다(물론 1이 해당 요소 중 하나가 되는 것을 허용하지 않음).이 단계가 실패하면 숫자는 소수이고 답은 여러분에게 있습니다!그렇지 않으면 두 가지 요소를 대기열에 추가하고 반복합니다.
다른 팁
내가 아는 최고의 알고리즘은 다음과 같습니다(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 factors
pfs = 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 factors
pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list
내 대답은 다음을 기반으로합니다. 삼부작하지만 많이 개선되었습니다.이는 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;
}
나는 최근에 다음과 같은 글을 썼습니다. 블로그 기사 이 알고리즘이 어떻게 작동하는지 설명합니다.
나는 원시성에 대한 테스트가 필요 없는 방법(및 체 구성 없음)이 이를 사용하는 방법보다 더 빠르게 실행될 것이라고 감히 생각합니다.그렇다면 아마도 여기에서 가장 빠른 알고리즘일 것입니다.
자바스크립트 코드:
'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);
모든 숫자는 소수의 곱으로 표현될 수 있습니다. 예:
102 = 2 x 3 x 17
712 = 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 with
for (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.
}
//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
}
@Triptych 답변과 비슷하지만 다릅니다.이 예에서는 목록이나 사전이 사용되지 않습니다.코드는 Ruby로 작성되었습니다.
def largest_prime_factor(number)
i = 2
while number > 1
if number % i == 0
number /= i;
i -= 1
end
i += 1
end
return i
end
largest_prime_factor(600851475143)
# => 6857
가장 간단한 해결책은 한 쌍의 것입니다. 상호 재귀적 기능.
첫 번째 함수는 모든 소수를 생성합니다.
- 1보다 큰 모든 자연수 목록으로 시작합니다.
- 소수가 아닌 모든 숫자를 제거합니다.즉, 자신 외에는 소인수가 없는 숫자입니다.아래를 참조하세요.
두 번째 함수는 주어진 숫자의 소인수를 반환합니다. n 증가하는 순서로.
- 모든 소수의 목록을 작성하십시오(위 참조).
- 인수가 아닌 모든 숫자를 제거합니다.
n.
가장 큰 소인수 n 두 번째 함수에 의해 주어진 마지막 숫자입니다.
이 알고리즘에는 게으른 목록 또는 언어(또는 데이터 구조) 필요에 따라 전화 의미론.
명확하게 설명하기 위해 Haskell에서 위의 구현을 (비효율적으로) 구현했습니다.
import Control.Monad
-- All the primes
primes = 2 : filter (ap (<=) (head . primeFactors)) [3,5..]
-- Gives the prime factors of its argument
primeFactors = 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 argument
largestFactor = last . primeFactors
이를 더 빠르게 만드는 것은 어떤 숫자가 소수인지 및/또는 다음의 인수를 감지하는 데 더 영리한 문제일 뿐입니다. 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에 대해서만 소수만 허용할 수 있습니다. 이는 여기에 있는 다른 답변에 나와 있습니다.
실제로 에라토스테네스의 체를 여기에 엮을 수 있습니다.
- 먼저 최대 sqrt (n)까지 정수 목록을 만듭니다.
- for 루프에서 i의 모든 배수는 새로운 sqrt (n)까지의 모든 배수를 프라임이 아닌 것으로 표시하고 대신 while 루프를 사용하십시오.
- 목록의 다음 소수로 i를 설정하십시오.
또한 참조하십시오 이 질문.
나는 이것이 빠른 해결책이 아니라는 것을 알고 있습니다.느린 솔루션을 이해하기 쉽도록 게시하십시오.
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;
}
숫자에서 모든 소인수를 제거하는 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
나는 숫자를 현재 소인수로 계속 나누는 알고리즘을 사용하고 있습니다.
Python 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 last
print(PrimeFactor(int(input())))
입력 : 10출력 : 5
입력 : 600851475143 출력 : 6857
다음은 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;
}
}
}
#python implementation
import math
n = 600851475143
i = 2
factors=set([])
while i<math.sqrt(n):
while n%i==0:
n=n/i
factors.add(i)
i+=1
factors.add(n)
largest=max(factors)
print factors
print 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
}
가장 큰 소인수를 빠르게 계산하는 방법은 다음과 같습니다.수정된 사실을 토대로 작성되었습니다. 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 factor
g x = f 2 x 2
다음 C++ 알고리즘은 최고는 아니지만 10억 미만의 숫자에 대해 작동하며 매우 빠릅니다.
#include <iostream>
using namespace std;
// ------ is_prime ------
// Determines if the integer accepted is prime or not
bool 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;
}
"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;
}
주어진 알고리즘의 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 = Test
3c) Goto 3.
4) Inc(Test)
5) If Current < Test goto 4
6) Return Largest
이 버전은 Sieve보다 90배 빠릅니다.
문제는 최신 프로세서에서는 작업 유형이 작업 수보다 훨씬 덜 중요하다는 것입니다. 위의 알고리즘은 캐시에서 실행될 수 있지만 Sieve는 그렇지 않다는 점은 말할 것도 없습니다.Sieve는 모든 합성수를 제거하는 많은 작업을 사용합니다.
또한 식별된 요소를 구분하면 테스트해야 하는 공간이 줄어듭니다.
소수를 먼저 저장하는 목록을 계산합니다.2 3 5 7 11 13 ...
숫자를 소인수분해할 때마다 Triptych의 구현을 사용하되 자연 정수가 아닌 소수 목록을 반복합니다.
자바의 경우:
을 위한 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;
}
이것은 아마도 항상 더 빠르지는 않지만 큰 소수 제수를 찾는 것에 대해 더 낙관적입니다.
N당신 전화번호예요- 만약 프라임이라면
return(N) - 까지 소수를 계산하세요.
Sqrt(N) - 내림차순으로 소수를 살펴봅니다. (가장 큰 것부터)
- 만약에
N is divisible by Prime그 다음에Return(Prime)
- 만약에
편집하다:3단계에서는 에라토스테네스의 체나 앳킨스의 체 등 원하는 것을 사용할 수 있지만 체 자체만으로는 가장 큰 소인수를 찾을 수 없습니다.(그래서 내가 SQLMenace의 게시물을 공식적인 답변으로 선택하지 않는 이유입니다...)
나는 n보다 작은 가능한 모든 소수를 어딘가에 저장하고 가장 큰 약수를 찾기 위해 반복하는 것이 좋을 것이라고 생각합니다.당신은 프라임을 얻을 수 있습니다 prime-numbers.org.
물론 나는 당신의 숫자가 너무 크지 않다고 가정합니다 :)
가장 빠르지는 않지만 작동합니다!
static bool IsPrime(long num)
{
long checkUpTo = (long)Math.Ceiling(Math.Sqrt(num));
for (long i = 2; i <= checkUpTo; i++)
{
if (num % i == 0)
return false;
}
return true;
}
다음은 생성기로 제공되는 동일한 function@Triptych이며 약간 단순화되었습니다.
def primes(n):
d = 2
while (n > 1):
while (n%d==0):
yield d
n /= d
d += 1
최대 소수는 다음을 사용하여 찾을 수 있습니다.
n= 373764623
max(primes(n))
다음을 사용하여 찾은 요소 목록:
list(primes(n))
#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();
}
