-3

https://www.geeksforgeeks.org/primality-test-set-1-introduction-and-school-method/

// 数値が素数かどうかをチェックする // 最適化された学校メソッド ベースの C++ プログラム

#include <bits/stdc++.h> 
using namespace std; 

bool isPrime(int n) 
{ 
    // Corner cases 
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 

    // This is checked so that we can skip  
    // middle five numbers in below loop 
    if (n%2 == 0 || n%3 == 0) return false; 

    for (int i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 

    return true; 
}
4

2 に答える 2

0

合成数には、その平方根以下の係数が少なくとも 1 つあります。なんで？因数が 1 つしかない場合 (それ自体または 1 つ以外)、それはその平方根に等しいからです。2 つ以上ある場合、最小のものはその平方根より小さくなければなりません。したがって、平方根より大きい数をチェックする必要はありません。素数でない場合は、すでに因数が見つかっているはずです。

コードは早い段階で因数として 2 または 3 をチェックします。後は、2 や 3 の倍数ではない要因をチェックするだけです。したがって、5 と 7 をチェックした後は、6、8、9、または 10 をチェックする必要はありません。したがって、6 つの数字のうち、2 または 3 の倍数でない 2 つだけをチェックする必要があります。

于 2019-03-05T19:49:33.333 に答える