数値の最大の素因数を見つけるアルゴリズム
https://stackoverflow.com/questions/23287
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
数値の最大の素因数を計算する最良の方法は何ですか?
最も効率的なのは次のとおりだと思います。
- きれいに割れる最小の素数を見つける
- 除算の結果が素数かどうかを確認する
- そうでない場合は、次に低い値を見つけます
- 2に進みます。
私はこの仮定に基づいて、小さな素因数を計算する方が簡単であると考えています。これは大体正しいでしょうか？他にどのようなアプローチを検討する必要がありますか?
編集：結果が他の 2 つの素因数の積である場合、ステップ 2 が失敗するため、3 つ以上の素因数が存在する場合、私のアプローチは無駄であることがわかりました。したがって、再帰的アルゴリズムが必要です。
再度編集します:そして今、これがまだ機能することに気づきました。最後に見つかった素数は最も大きいものでなければならないため、ステップ 2 の素数以外の結果をさらにテストすると、より小さな素数が得られることになります。
解決
実際には、大きな数の因数を見つけるためのより効率的な方法がいくつかあります (小さな数の場合、試行除算はかなりうまく機能します)。
入力数値の平方根に非常に近い 2 つの因数がある場合に非常に高速な 1 つの方法は、次のように知られています。 フェルマー因数分解. 。これは恒等式 N = (a + b)(a - b) = a^2 - b^2 を利用しており、理解と実装が簡単です。残念ながら、一般的にはそれほど高速ではありません。
最大 100 桁の数値を因数分解する最もよく知られた方法は、 二次ふるい. 。おまけに、アルゴリズムの一部は並列処理で簡単に実行できます。
私が聞いたことのあるさらに別のアルゴリズムは、 ポラードの Rho アルゴリズム. 。一般的に Quadratic Sieve ほど効率的ではありませんが、実装は簡単のようです。
数値を 2 つの因数に分割する方法を決定したら、数値の最大の素因数を見つけるために私が考えることができる最速のアルゴリズムを次に示します。
最初に番号自体を格納する優先キューを作成します。反復ごとに、キューから最大の数値を削除し、それを 2 つの要素に分割しようとします (もちろん、1 がそれらの要素の 1 つであることは許可されません)。このステップが失敗した場合、その数は素数であり、答えが得られます。それ以外の場合は、2 つの要素をキューに追加して繰り返します。
他のヒント
これが私が知っている中で最高のアルゴリズムです（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;
}
最近書きました ブログ記事 このアルゴリズムがどのように機能するかを説明します。
あえて言えば、素数性のテスト (およびふるいの構築) を必要としない方法の方が、素数性を使用する方法よりも高速に実行できると思います。その場合、これがおそらくここで最も高速なアルゴリズムです。
JavaScript コード:
'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 より大きいすべての自然数のリストから始めます。
- 素数ではない数字をすべて削除します。つまり、（それ自体以外に）素因数を持たない数値です。以下を参照してください。
2 番目の関数は、指定された数値の素因数を返します。 n 昇順で。
- すべての素数のリストを取得します (上記を参照)。
- ～の因数ではない数字をすべて削除します。
n.
の最大の素因数は、 n は 2 番目の関数によって与えられる最後の数値です。
このアルゴリズムには、 怠惰なリスト または言語 (またはデータ構造) 必要に応じて電話をかける セマンティクス。
明確にするために、Haskell での上記の (非効率的な) 実装の 1 つを次に示します。
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ループを使用します。
- リストの次の素数に設定します。
こちらもご覧ください この質問.
これが迅速な解決策ではないことは承知しています。遅い解決策をより簡単に理解できることを願って投稿します。
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 要因が見つかり次第。後は、最大の要素を返すだけです。それはもう全盛期だろう。
コード (Haskell):
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;
}
Web 上で「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;
}
sieve を使用した素因数:
#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 を因数分解するプログラムを 2 つ書きました。1 つは Sieve に基づいており、もう 1 つは以下に基づいています。
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 による実装を使用しますが、自然整数ではなく、この素数のリストを繰り返します。
Java の場合:
のために 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より小さいすべての可能な素数をどこかに保存し、それらを反復処理して最大の約数を見つけるのが良いと思います。素数は次から取得できます 素数.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;
}
以下は、ジェネレーターとして提供されている同じ関数 @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();
}
