素数性をテストするにはどうすればよいですか？
https://stackoverflow.com/questions/627463
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私は、いくつかの素数に関連するメソッドを持つ小さなライブラリを書いています。基礎（作業方法とも呼ばれます）を終えた今、いくつかの最適化を探しています。 もちろん、インターネットはそうするのに最適な場所です。しかし、丸めの問題につまずいたので、これをどのように解決するのか疑問に思っていました。
ループでは、素数の数をテストするために使用します。n/ 2またはn-1の代わりにsqrt（n）まで検索する方が効率的です。スキップ！たとえば、10000番目の素数は104729である必要がありますが、「最適化された」バージョンは103811になります。
一部のコード（最適化のために開かれていますが、一度に処理できるのは一度に1つだけです）：
/// <summary>
/// Method for testing the primality of a number e.g.: return IsPrime(29);
/// History:
/// 1. Initial version, most basic form of testing: m smaller then n -1
/// 2. Implemented m smaller then sqrt(n), optimization due to prime factoring
/// </summary>
/// <param name="test">Number to be tested on primality</param>
/// <returns>True if the number is prime, false otherwise</returns>
public static bool IsPrime(int test)
{
// 0 and 1 are not prime numbers
if (test == 0 || test == 1) return false;
// 2 and 3 are prime numbers
if (test == 2) return true;
// all even numbers, save 2, are not prime
if (test % 2 == 0) return false;
double squared = Math.Sqrt(test);
int flooredAndSquared = Convert.ToInt32(Math.Floor(squared));
// start with 5, make increments of 2, even numbers do not need to be tested
for (int idx = 3; idx < flooredAndSquared; idx++)
{
if (test % idx == 0)
{
return false;
}
}
return true;
}
2乗した部分が失敗する（または失敗する）ことはわかっていますが、Math.Ceilingも試してみましたが、ほぼ同じ結果が得られました。
解決
残念ながら、私は以前にアルゴリズムによるアプローチを試したことがありません。ただし、アプローチを効率的に実装する場合は、キャッシュを行うことをお勧めします。定義されたしきい値よりも小さいすべての素数を格納する配列を作成し、この配列を埋めて、その中を検索/使用します。
次の例では、数値が素数であるかどうかを調べるのが最良の場合（つまり、数値が maxPrime 以下、つまり64Kで821,461の場合）です。バッファ）、およびその他の場合に多少最適化されています（最初の820,000のうち64Kのみのmodをチェックすることで-約8％）。
（注：この回答を「最適な」アプローチとして受け取らないでください。実装を最適化する方法の例です。）
public static class PrimeChecker
{
private const int BufferSize = 64 * 1024; // 64K * sizeof(int) == 256 KB
private static int[] primes;
public static int MaxPrime { get; private set; }
public static bool IsPrime(int value)
{
if (value <= MaxPrime)
{
return Array.BinarySearch(primes, value) >= 0;
}
else
{
return IsPrime(value, primes.Length) && IsLargerPrime(value);
}
}
static PrimeChecker()
{
primes = new int[BufferSize];
primes[0] = 2;
for (int i = 1, x = 3; i < primes.Length; x += 2)
{
if (IsPrime(x, i))
primes[i++] = x;
}
MaxPrime = primes[primes.Length - 1];
}
private static bool IsPrime(int value, int primesLength)
{
for (int i = 0; i < primesLength; ++i)
{
if (value % primes[i] == 0)
return false;
}
return true;
}
private static bool IsLargerPrime(int value)
{
int max = (int)Math.Sqrt(value);
for (int i = MaxPrime + 2; i <= max; i += 2)
{
if (value % i == 0)
return false;
}
return true;
}
}
他のヒント
これはあなたの問題だと思います：
for (int idx = 3; idx < flooredAndSquared; idx++)
これは次のようになります
for (int idx = 3; idx <= flooredAndSquared; idx++)
したがって、素数として平方数を取得しません。また、「idx + = 2」を使用できます。 ＆quot; idx ++＆quot;の代わりにテストする必要があるのは奇数だけだからです（上のコメントで書いたように...）。
これが本当にあなたが探しているものかどうかはわかりませんが、本当に速度が気になる場合は、ふるいを使うのではなく、素数性をテストする確率論的な方法を検討する必要があります。 Rabin-Miller は、Mathematicaで使用される確率的素数テストです。
シーブまたはエラトステネスを使用して素数を計算するクラスをここに投稿しました：
マークが言ったように、Miller-Rabinテストは実際には非常に良い方法です。追加のリファレンス（擬似コード付き）は、ウィキペディアの記事です。それ。
確率的ですが、ごく少数のケースをテストするだけで、int（およびほぼ長い）範囲の数値に対して素数であるかどうかを判断できます。 ウィキペディアの記事のこの部分、または Primality Proving reference で詳細を確認してください。
モジュラーべき乗に関するこの記事も読むことをお勧めします。 Miller-Rabinテストを実行しようとするときに非常に大きな数に対処するために...
Fermatの小さな定理をご覧ください。
こちらは、本 S. Dasgupta、C.H.のアルゴリズムの擬似コードです。 Papadimitriou、およびU.V. Vazirani 、nは素数性をテストする数です。
Pick a positive integer a < n at random
if a^n-1 is equivalent to 1 (mod n)
return yes
else
return no
Fermatの定理の実装は、Sieveソリューションよりも高速です。ただし、フェルマーの検定に合格し、素数ではないカーマイケル数があります。これには回避策があります。 前述の本のセクション1.3 を参照することをお勧めします。それはすべて素数テストについてであり、あなたに役立つかもしれません。
試してみてください...
if (testVal == 2) return true;
if (testVal % 2 == 0) return false;
for (int i = 3; i <= Math.Ceiling(Math.Sqrt(testVal)); i += 2)
{
if (testVal % i == 0)
return false;
}
return true;
これを何度も使用しました。.ふるいほど高速ではありませんが、動作します。
オイラーの1つを解決するために作成した中途半端な関数を次に示します。
private static long IsPrime(long input)
{
if ((input % 2) == 0)
{
return 2;
}
else if ((input == 1))
{
return 1;
}
else
{
long threshold = (Convert.ToInt64(Math.Sqrt(input)));
long tryDivide = 3;
while (tryDivide < threshold)
{
if ((input % tryDivide) == 0)
{
Console.WriteLine("Found a factor: " + tryDivide);
return tryDivide;
}
tryDivide += 2;
}
Console.WriteLine("Found a factor: " + input);
return -1;
}
}
素数をチェックするための高速アルゴリズムがあります。素数の形式が6k＆＃177;であることがわかっている場合は、アルゴリズムを改善できます。 1、2と3を除く。したがって、最初に入力が2または3で割り切れるかどうかをテストできます。次に、フォーム6k＆＃177;のすべての数値を確認します。 1＆＃8804; ＆＃8730; input。
bool IsPrime(int input)
{
//2 and 3 are primes
if (input == 2 || input == 3)
return true;
else if (input % 2 == 0 || input % 3 == 0)
return false; //Is divisible by 2 or 3?
else
{
for (int i = 5; i * i <= input; i += 6)
{
if (input % i == 0 || input % (i + 2) == 0)
return false;
}
return true;
}
}
エラトステネスのふるいを試してください-ルートと浮動小数点を取得する必要があります問題。
floor については、 ceiling を使用することで対応できます。
private static bool IsPrime(int number) {
if (number <= 3)
return true;
if ((number & 1) == 0)
return false;
int x = (int)Math.Sqrt(number) + 1;
for (int i = 3; i < x; i += 2) {
if ((number % i) == 0)
return false;
}
return true;
}
これ以上速く取得できません...
素数と素数のテスト有用であり、AKSアルゴリズムは、確率ベースのテストと比較して特に実用的ではない場合でも、面白そうです。
これは素数のテスト（vb.net）で非常に高速に動作します
Dim rnd As New Random()
Const one = 1UL
Function IsPrime(ByVal n As ULong) As Boolean
If n Mod 3 = 0 OrElse n Mod 5 = 0 OrElse n Mod 7 = 0 OrElse n Mod 11 = 0 OrElse n Mod 13 = 0 OrElse n Mod 17 = 0 OrElse n Mod 19 = 0 OrElse n Mod 23 = 0 Then
return false
End If
Dim s = n - one
While s Mod 2 = 0
s >>= one
End While
For i = 0 To 10 - 1
Dim a = CULng(rnd.NextDouble * n + 1)
Dim temp = s
Dim m = Numerics.BigInteger.ModPow(a, s, n)
While temp <> n - one AndAlso m <> one AndAlso m <> n - one
m = (m * m) Mod n
temp = temp * 2UL
End While
If m <> n - one AndAlso temp Mod 2 = 0 Then
Return False
End If
Next i
Return True
End Function
他の誰かが興味を持っている場合のために、上記のMohammadの手順をVBAに変換します。 1、0、および負の数はすべて素数として定義されていないため、除外するチェックを追加しました。
Excel VBAでのみこれをテストしました：
Function IsPrime(input_num As Long) As Boolean
Dim i As Long
If input_num < 2 Then '1, 0, and negative numbers are all defined as not prime.
IsPrime = False: Exit Function
ElseIf input_num = 2 Then
IsPrime = True: Exit Function '2 is a prime
ElseIf input_num = 3 Then
IsPrime = True: Exit Function '3 is a prime.
ElseIf input_num Mod 2 = 0 Then
IsPrime = False: Exit Function 'divisible by 2, so not a prime.
ElseIf input_num Mod 3 = 0 Then
IsPrime = False: Exit Function 'divisible by 3, so not a prime.
Else
'from here on, we only need to check for factors where
'6k ± 1 = square root of input_num:
i = 5
Do While i * i <= input_num
If input_num Mod i = 0 Then
IsPrime = False: Exit Function
ElseIf input_num Mod (i + 2) = 0 Then
IsPrime = False: Exit Function
End If
i = i + 6
Loop
IsPrime = True
End If
End Function
forループは次のようになります。
for (int idx = 3; idx * idx <= test; idx++) { ... }
これにより、浮動小数点計算を回避できます。より高速に実行する必要があり、より正確になります。これが、 for ステートメントの条件が単なるブール式である理由です。これにより、このようなことが可能になります。
