Xが素数であるかどうかを判別でき、単なる人間プログラマーを混乱させない単純なアルゴリズムはありますか？

https://stackoverflow.com/questions/188425

06-07-2019
|

質問

Project Eulerを使って作業を進めていますが、その一部として素数を特定するように求めるいくつかの問題に気づきました。

xを2、3、4、5、...、Xの平方根で除算できることを知っています。平方根に到達した場合、（安全に）数が素数であると仮定できます。残念ながら、この解決策は非常にぎこちないようです。
数値が素数であるかどうかを判断する方法について、より良いアルゴリズムを検討しましたが、すぐに混乱してしまいます。

Xが素数であるかどうかを判断でき、単なる人間のプログラマを混乱させない単純なアルゴリズムはありますか？

ありがとう！

解決

最初のアルゴリズムは非常に優れており、Project Eulerで多く使用されました。必要な最大数がわかっている場合は、エラトステネスのふるいも調査できます。

素数のリストを維持する場合、最初のアルゴリズムを洗練して、数の平方根まで素数のみで除算することもできます。

これら2つのアルゴリズム（分割とふるい）を使用すると、問題を解決できるはずです。

編集：コメントに記載されている固定名

他のヒント

制限未満のすべての素数を生成するにはエラトステネスのふるい（ページには、 20のプログラミング言語）は最も古く、最もシンプルなソリューションです。

Pythonの場合：

def iprimes_upto(limit):
    is_prime = [True] * limit
    for n in range(2, limit):
        if is_prime[n]:
           yield n
           for i in range(n*n, limit, n): # start at ``n`` squared
               is_prime[i] = False

例：

>>> list(iprimes_upto(15))
[2, 3, 5, 7, 11, 13]

Fermatの素数性テストはすでに提案されているようですが、コンピュータープログラムの構造と解釈、および Miller-Rabin別の選択肢としてtest （セクション1.2.6、問題1.28を参照）。オイラー問題のために私はそれを成功裏に使用してきました。

これは、エラトステネスのふるいではないが、実装が非常に簡単なメソッドの単純な最適化です。最初にXを2と3で除算してから、j = 1..sqrt（X）/ 6をループします。 6 * j-1と6 * j + 1で除算しようとしています。これにより、2または3で割り切れるすべての数値が自動的にスキップされ、非常に優れた定数係数加速が得られます。

次の事実に留意してください（ MathsChallenge.net から）：

2を除くすべての素数は奇数です。
3より大きいすべての素数は、6k-1または6k + 1の形式で記述できます。
nの平方根を過ぎて確認する必要はありません

これは、比較的小さなnに使用するC ++関数です。

bool isPrime(unsigned long n)
{
    if (n == 1) return false; // 1 is not prime
    if (n < 4) return true; // 2 and 3 are both prime
    if ((n % 2) == 0) return false; // exclude even numbers
    if (n < 9) return true; //we have already excluded 4, 6, and 8.
    if ((n % 3) == 0) return false; // exclude remaining multiples of 3

    unsigned long r = floor( sqrt(n) );
    unsigned long f = 5;
    while (f <= r)
    {
        if ((n % f) == 0)  return false;
        if ((n % (f + 2)) == 0) return false;
        f = f + 6;
    }
    return true; // (in all other cases)
}

おそらく、独自の最適化をさらに考えることができます。

Fermatの素数性テストをお勧めします。これは確率的なテストですが、驚くほど頻繁に正しいです。そして、それはふるいと比較すると非常に高速です。

適度に小さい数値の場合、最大sqrt（x）のx％nは非常に高速で簡単にコーディングできます。

単純な改善：

テスト2と奇数のみ。

テスト2、3、および6 +または-1の倍数（2または3以外のすべての素数は6 +/- 1の倍数であるため、基本的にすべての偶数と3の倍数をすべてスキップしています

素数のみをテストします（sqrt（x）までのすべての素数を計算または保存する必要があります）

sieveメソッドを使用すると、任意の制限までの素数のリストをすばやく生成できますが、メモリを集中的に使用する傾向があります。 6の倍数のトリックを使用して、メモリ使用量を数字あたり1/3ビットまで減らすことができます。

6 + 1の倍数と6-1の倍数に2つのビットフィールドを使用する単純な素数クラス（C＃）を作成し、単純なルックアップを実行します...テストしている数値がふるい、それから2、3、および6 +/- 1のテストでフォールバックします。大きなふるいを生成することは、私が解決したほとんどのオイラー問題について、その場で素数を計算するよりも実際に時間がかかることがわかりました。これまでのところ。 KISSの原則が再び登場！

ふるいを使用してより小さな素数を事前計算する素数クラスを作成し、ふるいの範囲外のものについては、2、3、および6 +/- 1の倍数によるテストに依存しています。

プロジェクトオイラーにとって、素数のリストは本当に重要です。各問題に使用するリストを維持することをお勧めします。

探しているのはエラトステネスのふるいです。

あなたの右のシンプルは最も遅いです。ある程度最適化できます。

平方根の代わりにモジュラスの使用を検討してください。プライムを追跡します。 6は2と3の倍数であり、4は2の倍数であるため、7を2、3、5で除算するだけです。

Rsliteは eranthenosふるいについて言及しました。それはかなり簡単です。私はいくつかの言語でそれを家に持っています。後でそのコードを投稿したい場合はコメントを追加してください。

これが私のC ++です。改善する余地は十分にありますが、動的言語バージョンに比べて高速です。

// Author: James J. Carman
// Project: Sieve of Eratosthenes
// Description: I take an array of 2 ... max values. Instead of removeing the non prime numbers,
// I mark them as 0, and ignoring them.
// More info: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
#include <iostream>

int main(void) {
        // using unsigned short.
        // maximum value is around 65000
        const unsigned short max = 50000;
        unsigned short x[max];
        for(unsigned short i = 0; i < max; i++)
                x[i] = i + 2;

        for(unsigned short outer = 0; outer < max; outer++) {
                if( x[outer] == 0)
                        continue;
                unsigned short item = x[outer];
                for(unsigned short multiplier = 2; (multiplier * item) < x[max - 1]; multiplier++) {
                        unsigned int searchvalue = item * multiplier;
                        unsigned int maxValue = max + 1;
                        for( unsigned short maxIndex = max - 1; maxIndex > 0; maxIndex--) {
                                if(x[maxIndex] != 0) {
                                        maxValue = x[maxIndex];
                                        break;
                                }
                        }
                        for(unsigned short searchindex = multiplier; searchindex < max; searchindex++) {
                                if( searchvalue > maxValue )
                                        break;
                                if( x[searchindex] == searchvalue ) {
                                        x[searchindex] = 0;
                                        break;
                                }
                        }
                }
        }
        for(unsigned short printindex = 0; printindex < max; printindex++) {
                if(x[printindex] != 0)
                        std::cout << x[printindex] << "\t";
        }
        return 0;
}

見つけた後すぐに、Perlとpythonのコードを破棄します。それらはスタイルが似ており、行が少なくなっています。

D（デジタル火星）の簡単な素数性テストは次のとおりです。

/** 
 * to compile:
 * $ dmd -run prime_trial.d
 * to optimize:
 * $ dmd -O -inline -release prime_trial.d 
 */
module prime_trial;

import std.conv : to;  
import std.stdio : w = writeln;

/// Adapted from: http://www.devx.com/vb2themax/Tip/19051 
bool 
isprime(Integer)(in Integer number) 
{
  /* manually test 1, 2, 3 and multiples of 2 and 3 */
  if (number == 2 || number == 3)
    return true;
  else if (number < 2 || number % 2 == 0 || number % 3 == 0)
    return false;

  /* we can now avoid to consider multiples 
   * of 2 and 3. This can be done really simply 
   * by starting at 5 and incrementing by 2 and 4 
   * alternatively, that is: 
   *    5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...    
   * we don't need to go higher than the square root of the number */
  for (Integer divisor = 5, increment = 2; divisor*divisor <= number; 
       divisor += increment, increment = 6 - increment) 
    if (number % divisor == 0)
      return false;

  return true;  // if we get here, the number is prime
}

/// print all prime numbers less then a given limit
void main(char[][] args) 
{
  const limit = (args.length == 2) ? to!(uint)(args[1]) : 100;
  for (uint i = 0; i < limit; ++i) 
    if (isprime(i))
      w(i);
}

私はプロジェクトオイラーの問題にも取り組んでおり、実際には、＃3（idによる）を終了しました。これは、複合数の最大素因数の検索です（？の数は600851475143です）。

素数に関する情報（ここで既に説明したSieveテクニック）、およびウィキペディアでの整数因数分解に関するすべての情報を見て、総当たりトライアル除算アルゴリズムを思い付きました。

だから私はルビーを学ぶためにオイラー問題をやっているので、アルゴリズムをコーディングしようとしていて、プライムクラスおよび prime_division メソッドを持つ整数クラス。なんてクールなのでしょう。このルビースニペットの問題に対する正しい答えを得ることができました：

require "mathn.rb"
puts 600851475143.prime_division.last.first

このスニペットは、コンソールに正しい答えを出力します。もちろん、この小さな美しさにつまずく前に、たくさんの読書と学習をしました。みんなと共有すると思っただけです...

このpythonコードが好きです。

def primes(limit) :
    limit += 1
    x = range(limit)
    for i in xrange(2,limit) :
        if x[i] ==  i:
            x[i] = 1
            for j in xrange(i*i, limit, i) :
                x[j] = i
    return [j for j in xrange(2, limit) if x[j] == 1]

これのバリアントを使用して、数値の因子を生成できます。

def factors(limit) :
    limit += 1
    x = range(limit)
    for i in xrange(2,limit) :
        if x[i] == i:
            x[i] = 1
            for j in xrange(i*i, limit, i) :
                x[j] = i
    result = []
    y = limit-1
    while x[y] != 1 :
        divisor = x[y]
        result.append(divisor)
        y /= divisor
    result.append(y)
    return result

もちろん、数値のバッチを因数分解する場合、キャッシュを再計算しません。私は一度それをして、その中で検索を行います。

最適化されていませんが、非常に単純な関数です。

    function isprime(number){

    if (number == 1)
        return false;

    var times = 0;

    for (var i = 1; i <= number; i++){
        if(number % i == 0){
            times ++;
        }
    }
        if (times > 2){
            return false;
        }

    return true;
    }

たぶん、Javaでのこの実装は役に立つかもしれません：

public class SieveOfEratosthenes {

    /**
     * Calling this method with argument 7 will return: true true false false true false true false
     * which must be interpreted as : 0 is NOT prime, 1 is NOT prime, 2 IS prime, 3 IS prime, 4 is NOT prime
     * 5 is prime, 6 is NOT prime, 7 is prime.
     * Caller may either revert the array for easier reading, count the number of primes or extract the prime values
     * by looping.
     * @param upTo Find prime numbers up to this value. Must be a positive integer.
     * @return a boolean array where index represents the integer value and value at index returns
     * if the number is NOT prime or not.
     */
    public static boolean[] isIndexNotPrime(int upTo) {
        if (upTo < 2) {
            return new boolean[0];
        }

        // 0-index array, upper limit must be upTo + 1
        final boolean[] isIndexNotPrime = new boolean[upTo + 1];

        isIndexNotPrime[0] = true; // 0 is not a prime number.
        isIndexNotPrime[1] = true; // 1 is not a prime number.

        // Find all non primes starting from 2 by finding 2 * 2, 2 * 3, 2 * 4 until 2 * multiplier > isIndexNotPrime.len
        // Find next by 3 * 3 (since 2 * 3 was found before), 3 * 4, 3 * 5 until 3 * multiplier > isIndexNotPrime.len
        // Move to 4, since isIndexNotPrime[4] is already True (not prime) no need to loop..
        // Move to 5, 5 * 5, (2 * 5 and 3 * 5 was already set to True..) until 5 * multiplier > isIndexNotPrime.len
        // Repeat process until i * i > isIndexNotPrime.len.
        // Assume we are looking up to 100. Break once you reach 11 since 11 * 11 == 121 and we are not interested in
        // primes above 121..
        for (int i = 2; i < isIndexNotPrime.length; i++) {
            if (i * i >= isIndexNotPrime.length) {
                break;
            }
            if (isIndexNotPrime[i]) {
                continue;
            }
            int multiplier = i;
            while (i * multiplier < isIndexNotPrime.length) {
                isIndexNotPrime[i * multiplier] = true;
                multiplier++;
            }
        }

        return isIndexNotPrime;
    }

    public static void main(String[] args) {
        final boolean[] indexNotPrime = SieveOfEratosthenes.isIndexNotPrime(7);
        assert !indexNotPrime[2]; // Not (not prime)
        assert !indexNotPrime[3]; // Not (not prime)
        assert indexNotPrime[4]; // (not prime)
        assert !indexNotPrime[5]; // Not (not prime)
        assert indexNotPrime[6]; // (not prime)
        assert !indexNotPrime[7]; // Not (not prime)
    }
}

AKSプライムテストアルゴリズム：

Input: Integer n > 1  


if (n is has the form ab with b > 1) then output COMPOSITE  

r := 2  
while (r < n) {  
    if (gcd(n,r) is not 1) then output COMPOSITE  
    if (r is prime greater than 2) then {  
        let q be the largest factor of r-1  
        if (q > 4sqrt(r)log n) and (n(r-1)/q is not 1 (mod r)) then break  
    }  
    r := r+1  
}  

for a = 1 to 2sqrt(r)log n {  
    if ( (x-a)n is not (xn-a) (mod xr-1,n) ) then output COMPOSITE  
}  

output PRIME;

Pythonの別の方法：

import math

def main():
    count = 1
    while True:
        isprime = True

        for x in range(2, int(math.sqrt(count) + 1)):
            if count % x == 0: 
                isprime = False
                break

        if isprime:
            print count


        count += 2


if __name__ == '__main__':
    main()

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow