素因数分解アルゴリズム: C, Python 例

替え： サラ・チェン サラ・チェン
Hours 更新中

素因数分解とは何ですか?

特定の素因数 どれか 数値は要素です 素数。 因数を乗算すると、別の数値が得られます。 素数はそれ自身または 1 で割り切れます。

言い換えれば、どの素数を掛け合わせると元の数になるかを見つけることで素因数が決定されます。

例: 10 の素因数は 2 と 5 です。これは、2X5 =10 であり、2,5 と XNUMX は両方とも素数であるためです。

反復を使用して素因数を見つける

与えられた数の素因数を見つけるには、まず 2 からその数の平方根までのすべての数を反復し、各数が素数かどうかを確認します。元の数がこの素数で割り切れる限り、反復ごとにこの素数を加算し続けます。

例：

40より大きい素数はすべて次の式で表されます。n2+n+41。したがって、nをすべての数字に置き換えて、対応する素因数を求めることができます。例：02+0+41=41、12+1+41=43、22+2+41=47、…

数値の素因数を出力するにはどうすればよいですか?

  • この方法では、前のセクションで説明したように、2 から数値の平方根まで数値を反復処理します。
  • そのためには、 2 から n の平方根までの各数値について、元の数値の係数を確認する必要があります。
  • 次に、n の因数となる素数のリストを見つけます。
  • このソリューションは O(Sqrt(n)) の時間計算量です。

アルゴリズム：

Set a counter i  to 2
While i  <= sqrt(n):
	While n% i  == 0:
		n = n / i  
		print i  
	i  = i  +1
if n > 1:
	print n

ふるいアルゴリズム

ふるい法は、数値の最小の素因数を保存することに依存しており、これにより、任意の数値の素因数を計算する際の複雑さが大幅に軽減されます。ふるいアルゴリズムは、すべての素因数をある程度効率的に見つけます。

  • このアルゴリズムの主な概念は、各数値の最小の素因数を最大数値まで保存することです。
  • 与えられた各数値の最小の素数を取得し、それを素因数のセットに追加します。
  • 最後に、この素​​数で割り、1 に達するまでこれらの手順を繰り返します。
  • これはすべて O(log(n)) の時間計算量で実行され、ソリューションの効率が大幅に向上します。
  • これにより、以前のアプローチで処理できたよりもはるかに大きな数の素因数を計算することが可能になります。

例：

6 番目の方法は、1 と 6 以外の素数を 1 つの式のいずれかに記述する必要があるため、その数値が 2n-3 または 5n+6 として記述できるかどうかを確認することです。 例: 1=1(19)-6、3=1(XNUMX)+XNUMX、… 。

アルゴリズム：

配列 array を定義して、各数値の最小の素因数を格納し、インデックス値を初期値として各数値のすべての要素に使用します。 配列.

Set array[1] to 1
Set i to 2
While i*i > max number:
	If array[i] == i:
		Set j to i*i
		While j > max number:
			If array[j] == j:
				Array[j] = i
			j = j + i
	i = i + 1
while the number != 1:
	print array[the number]
	the number = the number / array[the number]

関連記事

Python 反復法を使った素因数分解

ここでは、コードを紹介します Python 反復法で与えられた数の素因数を見つける言語:

import math
def PrimeFactors(n):
    for i in range(2,int(math.sqrt(n))+1,1):
        while n%i==0:#find all the occurrences of a prime factor
            print((int)(i)),
            n=n/i
    if n!=1:#if the number was originally a prime
        print((int)(n))
n=(int)(input("Enter the number you want: "))
PrimeFactors(n)

出力：

Enter the number you want: 4
4

Python 再帰を使った素因数分解

このセクションでは、次のコードを示します。 Python 言語 ふるい法を使用して、指定された数値の素因数を見つけます。

import math
High = (int)(1e5+7)
array=[0 for i in range(High)]
# function to generate all the smallest prime 
def Sieve():
#factors of the numbers until the maximum  number
    for i in range(1, High):
        array[i]=i
    for i in range(2, math.ceil(math.sqrt(High))):
        if (array[i] == i):
            for j in range(i*i, High,i):
                if(array[j]==j):
                    array[j]=i
def PrimeFactors(n):
#We will keep dividing until we reach 1
    if n == 1:
        return
    print((int)(array[n]))
    PrimeFactors((int)(n/array[n]))
#Here we call the function after dividing it by this prime
Sieve()
n=(int)(input("Enter the number you want: "))
PrimeFactors(n)

出力：

Enter the number you want: 4
2
2

反復を使用した C 素因数プログラム

これは反復的な Python のものと同じソリューションですが、次のように書かれています。 C言語.

ユーザーに数値を入力してもらい、2 からこの数値の平方根までの各数値について、この因数の出現をすべて出力して割り切れるかどうかを確認する必要があります。

#include <stdio.h>
int main()
{
    int n;
    printf("Enter the number you want: ");
    scanf("%d", &n);
    for(int i=2; i*i<=n; i++)
    {
        while(n%i==0)//find all the occurrences of a prime factor
        {
            printf("%d\n",i);
            n/=i;
        }
    }
    if(n!=1)//if the number was originally a prime
    {
        printf("%d",n);
    }
    return 0;
}

出力：

Enter the number you want: 2
2

再帰を使用した C 素因数プログラム

再帰を使用した C 素因数プログラム

これは Python の再帰的な解決策と同じですが、C で書かれています。

ユーザーに番号の入力を求めることができます。 次に、各数値の最小の素因数を格納する素数配列を構築します。 最後に、Prime Factors 再帰関数を呼び出します。この関数は、指定された数値を最小の素因数で割り、XNUMX に達するまでそれ自体を呼び出します。

#include <stdio.h>
int Max = 100007;
int array[100007];
void Sieve()//helping function to generate all the smallest //prime factors of the numbers until the maximum number
{
    for(int i=1;i<Max;i++)
    {
        array[i]=i;
    }
    for(int i=2;i*i<=Max;i++)
    {
        if(array[i]==i)
        {
            for(int j=i*i;j<Max;j+=i)
            {
                if(array[j]==j)
                {
                    array[j]=i;
                }
            }
        }
    }
}
void PrimeFactors(int n)
{
    if(n==1)//keep dividing until we reach 1
    {
        return;
    }
    printf("%d\n",array[n]);
    PrimeFactors(n/array[n]);//call the function after dividing by //this prime
}
int main()
{
    Sieve();
    int n;
    printf("Enter the number you want: ");
    scanf("%d", &n);
    PrimeFactors(n);
    return 0;
}

出力：

Enter the number you want: 2
2

素数に関する興味深い事実

  • 最も興味深い事実の 2 つは、XNUMX 以外の任意の偶数が XNUMX つの素数の和になる可能性があることです。
  • 例: 4 = 2 + 2、6 = 3 + 3、8 = 5 + 3 …など。
  • もう 2 つの事実は、偶数の素数は 3 だけであるため、2 と XNUMX 以外に連続する素数はないということです。
  • また、2 と 3 を除くすべての素数は、6 * n + 1 または 6 * n – 1 の形式で表すことができます。ここで、n は正の整数です。
  • 数値の素因数のセットは一意です。
  • 数値 1 は素数でも合成でもありません。
  • 数値の素因数分解は、割り切れるかどうか、分数の簡約、異なる分数の共通分母の検出などの問題を解決するのに役立ちます。
  • また、素因数分解の興味深い用途の XNUMX つは、数値ベースの秘密の暗号を解読することです。

よろしければ：