4

コード：

void prime()    
{    
    int i,N;    
    scanf("%d",&N);    
    for(i=2;i<N;i++)            
    {    
        if (((i^(N-1))%N )==1);     
        else{    
            printf("not prime");   
            return;
        }     
    }    
    printf("prime");    
    return;    
}

このプログラムは、素数に関するフェルマーの定理に基づいています。N は素数としてテストされる数です。このプログラムは、'11' に対して正しい結果を表示していません。たぶん、私が特定していない何らかの間違いが原因です。

4

4 に答える 4

0

コードを少し変更して申し訳ありません。BigInteger クラスを使用すると、はるかに大きな数値を非常に高速に計算できます。ただし、このメソッドを使用して素数を取得するのではなく、素数があるかどうかをテストできます。

using System;
using System.Numerics;
                    
public class Program
{
    public static void Main()
    {
        Console.WriteLine(2);
        for(var i = 3; i < 100000; i+=2) 
        {
            if(BigInteger.ModPow(2, i , i) == 2)
                Console.WriteLine(i);
        }
    }
}

https://dotnetfiddle.net/nwDP7h

このコードは、次の数値に該当する場合に誤った結果を生成します。

https://oeis.org/a001567 https://oeis.org/a006935

これらのエラーを修正するには、コードを次のように編集し、これらの数値内でバイナリ検索を実行して、数値が疑似素数かどうかをテストする必要があります。

public static bool IsPrime(ulong number)
{
    return number == 2
        ? true
        : (BigInterger.ModPow(2, number, number) == 2
            ? (number & 1 != 0 && BinarySearchInA001567(number) == false)
            : false)
}

public static bool BinarySearchInA001567(ulong number)
{
    // Is number in list?
    // todo: Binary Search in A001567 (https://oeis.org/A001567) below 2 ^ 64
    // Only 2.35 Gigabytes as a text file http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html
}
于 2020-07-19T00:21:36.743 に答える
0

モジュール化された数学的規則と原則をここに適用して、計算するためにそれを示すことができます

(i ^ (N-1)) % N,

そもそも i^(N-1) を計算する必要さえありません。(N-1) は簡単に2の累乗に分解できます。より明確にするために例を挙げてみましょう。

素数性テストの対象を N = 58 とします。

そう、

N - 1 = 57

57 は次のように簡単に書き換えることができます。

57 = 1 + 8 + 16 + 32

また、

57 = 2^0 + 2^3 + 2^4 + 2^5

したがって、この値をN-1に代入して、計算する必要があります

(i ^ (2^0 + 2^3 + 2^4 + 2^5))% 58

また、

((i^1) × (i^8) × (i^16) × (i^32))% 58

剰余乗算恒等式を使用すると、次のように書き換えることができます。

((i^1)% 58 × (i^8)% 58 × (i^16)% 58 × (i^32)% 58) mod 58 ---(1)

ご了承ください、

(i^1)% 58 = i%58

オーバーフローを心配することなく簡単に計算できます。

剰余乗算恒等式を再び利用すると、次のことがわかります。

(i^2)% 58 = ((i^1)% 58 × (i^1)% 58)% 58

(i^1)% 58 の値を代入して (i^2)% 58 を見つけます。

この方法で、(i^4)% 58 から (i^32)% 58 までの計算を続けることができます。完了すると、最終的に (1) の値を代入して必要な値を最終的に見つけることができ、オーバーフローを非常に効率的に回避できます。

他のべき剰余法も存在することに注意してください。これは、フェルマーの小さな素数性テストを実装する際にモジュール式の数学的手法をどのように使用できるかを示す例にすぎません。

乾杯！

于 2016-06-26T18:14:30.873 に答える