数が素数かどうかを判断する

algorithm c++ primes
数が素数かどうかを判断する

私はこのトピックに関する多くのコードを熟読しましたが、それらのほとんどは入力数までずっと素数である数を生成します。 ただし、指定された入力番号が素数かどうかのみをチェックするコードが必要です。

これは私が書くことができたものですが、動作しません:

void primenumber(int number)
{
    if(number%2!=0)
      cout<<"Number is prime:"<

この作業を適切に行う方法について誰かからアドバイスをいただければ幸いです。

更新

forループ内のすべての数値をチェックするように変更しました。

void primenumber(int number)
{
    for(int i=1; i

  10  9


ベストアンサー

bool isPrime(int number){

    if(number < 2) return false;
    if(number == 2) return true;
    if(number % 2 == 0) return false;
    for(int i=3; (i*i)<=number; i+=2){
        if(number % i == 0 ) return false;
    }
    return true;

}

34


有名なRabin-Millerアルゴリズムの決定論的な変形に基づいて記述され、独自のIsPrime()関数を最適化されたステップブルートフォーシングと組み合わせて、最速の素数テスト関数の1つを提供します。

__int64 power(int a, int n, int mod)
{
 __int64 power=a,result=1;

 while(n)
 {
  if(n&1)
   result=(result*power)%mod;
  power=(power*power)%mod;
  n>>=1;
 }
 return result;
}

bool witness(int a, int n)
{
 int t,u,i;
 __int64 prev,curr;

 u=n/2;
 t=1;
 while(!(u&1))
 {
  u/=2;
  ++t;
 }

 prev=power(a,u,n);
 for(i=1;i<=t;++i)
 {
  curr=(prev*prev)%n;
  if((curr==1)&&(prev!=1)&&(prev!=n-1))
   return true;
  prev=curr;
 }
 if(curr!=1)
  return true;
 return false;
}

inline bool IsPrime( int number )
{
 if ( ( (!(number & 1)) && number != 2 ) || (number < 2) || (number % 3 == 0 && number != 3) )
  return (false);

 if(number<1373653)
 {
  for( int k = 1; 36*k*k-12*k < number;++k)
  if ( (number % (6*k+1) == 0) || (number % (6*k-1) == 0) )
   return (false);

  return true;
 }

 if(number < 9080191)
 {
  if(witness(31,number)) return false;
  if(witness(73,number)) return false;
  return true;
 }


 if(witness(2,number)) return false;
 if(witness(7,number)) return false;
 if(witness(61,number)) return false;
 return true;

 /*WARNING: Algorithm deterministic only for numbers < 4,759,123,141 (unsigned int's max is 4294967296)
   if n < 1,373,653, it is enough to test a = 2 and 3.
   if n < 9,080,191, it is enough to test a = 31 and 73.
   if n < 4,759,123,141, it is enough to test a = 2, 7, and 61.
   if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11.
   if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13.
   if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17.*/
}

使用するには、コードをコピーしてプログラムの上部に貼り付けます。 呼び出すと、trueまたはfalseのBOOL値が返されます。

if(IsPrime(number))
{
    cout << "It's prime";
}

else
{
    cout<<"It's composite";
}

「__int64」を使用したコンパイルで問題が発生した場合は、「long」に置き換えてください。 VS2008およびVS2010で正常にコンパイルされます。

仕組み:関数には3つの部分があります。 パーツは、それがまれな例外(負の数、1)の1つであるかどうかを確認し、プログラムの実行をインターセプトします。

パート2は、数値が1373653より小さい場合に開始します。これは、理論的には、Rabin Millerアルゴリズムが最適化されたブルートフォース関数に勝る数値です。 次に、必要な証人の数を最小限に抑えるように設計された2レベルのRabin Millerが登場します。 テストするほとんどの数値は40億未満であるため、目撃者2、7、および61を確認することにより、確率論的ラビンミラーアルゴリズムを決定論的にすることができます。 40億の上限を超える必要がある場合は、多数のライブラリが必要になり、モジュラスまたはビットシフトの変更をpower()関数に適用します。

ブルートフォースメソッドを主張する場合、最適化されたブルートフォースIsPrime()関数のみを以下に示します。

inline bool IsPrime( int number )
{
 if ( ( (!(number & 1)) && number != 2 ) || (number < 2) || (number % 3 == 0 && number != 3) )
  return (false);

 for( int k = 1; 36*k*k-12*k < number;++k)
  if ( (number % (6*k+1) == 0) || (number % (6*k-1) == 0) )
   return (false);
  return true;
 }
}

このブルートフォースの仕組み:すべての素数(2と3を除く)は、6k + 1または6k-1の形式で表現できます。ここで、kは正の整数です。 このコードはこの事実を使用し、問題の数値の平方根よりも小さい6k + 1または6k-1の形式ですべての数値をテストします。 この部分は、より大きなIsPrime()関数(最初に示した関数)に統合されています。

数の下のすべての素数を見つける必要がある場合は、1000の下のすべての素数を見つけ、エラトステネスのふるいを調べます。 私のもう一つのお気に入り。

追加のメモとして、だれかが楕円曲線法アルゴリズムを実装することを楽しみにしています。しばらくの間C ++で実装されたものを見たいと思っていましたが、実装を失いました。 理論的には、実装した決定論的Rabin Millerアルゴリズムよりもさらに高速ですが、40億未満の数値に当てはまるかどうかはわかりません。

33


さらに確認する必要があります。 現時点では、数値が2で割り切れるかどうかのみを確認しています。 2、3、4、5、6、…​についても同じことを行います `number`まで。 ヒント:*ループ*を使用します。

これを解決したら、最適化を探してみてください。 ヒント:数値の平方根までのすべての数値をチェックするだけです

13


if(input%number!= 0)がfalseを返す場合、sqrtを取得し、foreachを2からsqrt + 1に実行すると思います。 sqrt + 1に到達すると、その素数を確認できます。

5


入力の範囲(関数が `int`を取得するために行う)がわかっている場合、最大入力の平方根(この場合は2 ^ 31-1)以下の素数のテーブルを事前計算できます。 )、次に、指定された数の平方根以下のテーブル内の各素数による分割可能性をテストします。

3


bool check_prime(int num) {
    for (int i = num - 1; i > 1; i--) {
        if ((num % i) == 0)
            return false;
    }
    return true;
}

素数の場合、任意の数をチェックします

3


  • C *

bool isPrime(int number){
    if (number != 2){
        if (number < 2 || number % 2 == 0) {
            return false;
        }
        for(int i=3; (i*i)<=number; i+=2){
            if(number % i == 0 ){
                return false;
            }
        }
    }
    return true;
}
  • Javascript *

function isPrime(number)
{
    if (number !== 2) {
        if (number < 2 || number % 2 === 0) {
            return false;
        }
        for (var i=3; (i*i)<=number; i+=2)
        {
            if (number % 2 === 0){
                return false;
            }
        }
    }
    return true;
}
  • Python *

def isPrime(number):
    if (number != 2):
        if (number < 2 or number % 2 == 0):
            return False
        i = 3
        while (i*i) <= number:
            if(number % i == 0 ):
                return False;
            i += 2
    return True;

3


このコードは、数値が2で割り切れるかどうかのみをチェックします。 数が素数であるためには、_それ自体よりも小さいすべての整数_で割り切れないようにする必要があります。 これは、ループ内の `floor(sqrt(n))`より小さいすべての整数で割り切れるかどうかをチェックすることで、単純に実装できます。 興味があるなら、http://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests [はるかに高速なアルゴリズム]が存在します。

2


怠け者でRAMが多い場合は、http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes [エラトステネスのふるい]を作成します。これは実質的に、素数でないすべての数字をキックした巨大な配列です。 それ以降、すべての主要な「確率」テストは非常に迅速になります。 高速な結果を得るためのこのソリューションの上限は、RAMの量です。 超低速の結果に対するこのソリューションの上限は、ハードディスクの容量です。

2


同じアルゴリズムに従いますが、ステップ2で奇数のみでsqrt(n)にループする異なる実装に従います。2または2 * kで割り切れる場合はfalseであることを確認するからです。 これが私のコードです

public class PrimeTest {

    public static boolean isPrime(int i) {
        if (i < 2) {
            return false;
        } else if (i % 2 == 0 && i != 2) {
            return false;
        } else {
            for (int j = 3; j <= Math.sqrt(i); j = j + 2) {
                if (i % j == 0) {
                    return false;
                }
            }
            return true;
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        for (int i = 1; i < 100; i++) {
            if (isPrime(i)) {
                System.out.println(i);
            }
        }
    }

}

2


タイトルとURLをコピーしました