506

数が素数であるかどうかをテストするには、なぜその数の平方根までしか除算できないかどうかをテストする必要があるのでしょうか。

4

13 に答える 13

832

数が素数でない場合、それは2つの要因にn因数分解することができます：ab

n = a * b

現在a、およびbの両方をの平方根より大きくすることはできません。nそれ以降、積a * bは。より大きくなりsqrt(n) * sqrt(n) = nます。したがって、の因数分解ではn、少なくとも1つの因数がの平方根よりも小さい必要があります。n平方根以下の因数が見つからない場合はn、素数である必要があります。

于 2011-04-27T22:04:05.237 に答える
374

m = sqrt(n)それでは、としましょうm × m = n。nが素数でない場合は、nと書くことができます。は実数であるのに対し、、は自然数であることに注意してください。n = a × bm × m = a × bmnab

現在、3つのケースが考えられます。

  1. a>m⇒b<m
  2. a=m⇒b=m
  3. a<m⇒b>m

3つのケースすべてで、min(a, b) ≤ m。したがって、まで検索するmと、の少なくとも1つの因子が見つかるはずです。これは、素数nではないことを示すのに十分です。n

于 2011-04-28T05:14:16.470 に答える
66

因子がnの平方根よりも大きい場合、nに等しくなるようにそれを乗算する他の因子は、必然的にnの平方根よりも小さくなるためです。

于 2011-04-27T22:04:09.717 に答える
26

素数n（1より大きい）ではないとします。だから数字などがaありbます

n = ab      (1 < a <= b < n)

a<=b関係にを掛けるaと、次のbようになります。

a^2 <= ab
 ab <= b^2

したがって:(注意してくださいn=ab）

a^2 <= n <= b^2

したがって:(aとbは正であることに注意してください）

a <= sqrt(n) <= b

したがって、数（1より大きい）が素数ではなく、数の平方根までの除算性をテストする場合、要因の1つが見つかります。

于 2015-07-30T23:39:00.497 に答える
9

それはすべて、因数分解と平方根の基本的な使用法です。

抽象的に見えるかもしれませんが、実際には、非素数の可能な最大階乗は、次の理由で平方根でなければならないという事実に基づいています。

sqrroot(n) * sqrroot(n) = n。

1とすると、上下または最大の整数sqrroot(n)が均等にに分割される場合、素数にすることはできませんn。n

擬似コードの例：

i = 2;

is_prime = true;

while loop (i <= sqrroot(n))
{
  if (n % i == 0)
  {
    is_prime = false;
    exit while;
  }
  ++i;
}
于 2015-11-28T01:28:06.660 に答える
8

N与えられた整数が素数ではないと仮定しましょう、

次に、Nは2つの因子aとbに 因数分解できます。明らかに、両方を同時に大きくすることはできません。2 <= a, b < NN = a*bsqrt(N)

一般性を失うことなく、より小さなものを想定しましょうa。

Nさて、範囲内に属する除数が見つからなかった場合、[2, sqrt(N)]それはどういう意味ですか？

これは、としてN除数がないことを意味します。[2, a]a <= sqrt(N)

したがって、したがって、したがって、a = 1定義b = n上、Nは素数です。

..。

満足できない場合は、さらに読んでください。

多くの異なる組み合わせが(a, b)可能かもしれません。彼らがそうだとしましょう：

（a 1、b 1）、（a 2、b 2）、（a 3、b 3）、.....、（a k、b k）。一般性を失うことなく、a i <b i、と仮定し1<= i <=kます。

さて、Nそれが素数ではないことを示すことができるためには、iのどれもそれ以上因数分解できないことを示すことで十分です。また、a i <=であることがわかっているため、すべてのaiをカバーsqrt(N)するまでチェックする必要があります。したがって、プライムであるかどうかを結論付けることができます。sqrt(N)N

..。

于 2017-07-09T19:41:09.547 に答える
7

素数ではない数「a」があるとしましょう[素数/合成数ではないということは、1またはそれ自体以外の数で均等に割ることができる数を意味します。たとえば、6は2、3、および1または6で均等に分割できます]。

6=1×6または6=2×3

したがって、「a」が素数でない場合は、他の2つの数で割ることができ、それらの数が「b」と「c」であるとしましょう。つまり、

a = b*c。

ここで、「b」または「c」の場合、それらのいずれかが「a」の平方根よりも大きく、「b」と「c」の乗算よりも「a」よりも大きくなります。

したがって、方程式「a = b * c」を証明するために、「b」または「c」は常に「a」の平方根未満です。

上記の理由により、数値が素数であるかどうかをテストする場合、その数値の平方根までのみチェックします。

于 2017-07-20T13:28:05.953 に答える
6

したがって、数値Nが素数であるかどうかを確認します。Nがnumbers<=SQROOT（N）で割り切れるかどうかを確認するだけで済みます。これは、Nを任意の2つの要素に因数分解すると、XとY、つまり、N = XY。XとYのそれぞれはSQROOT（N）より小さくすることはできません。その場合、X Y <N XとYのそれぞれはSQROOT（N）より大きくなることはできません。その場合、X * Y> N

したがって、一方の係数はSQROOT（N）以下である必要があります（もう一方の係数はSQROOT（N）以上である必要があります）。したがって、Nが素数であるかどうかを確認するには、これらの数値<= SQROOT（N）のみを確認する必要があります。

于 2017-05-10T13:43:00.453 に答える
3

nを非プライムとします。したがって、1より大きい少なくとも2つの整数因子があります。fをnのそのような因子の最小値とします。f>sqrtnと仮定します。その場合、n / fは整数≤sqrtnであるため、fよりも小さくなります。したがって、fをnの最小係数にすることはできません。帰謬法; nの最小係数は≤sqrtnでなければなりません。

于 2016-01-24T00:01:35.010 に答える
3

任意の数が与えられた場合n、その因子を見つける1つの方法は、その平方根を取得することpです。

sqrt(n) = p

もちろん、pそれ自体で乗算すると、元に戻りますn：

p*p = n

次のように書き直すことができます。

a*b = n

どこp = a = b。a増加する場合は、b減少して維持しa*b = nます。したがって、pが上限です。

更新：私は今日この答えをもう一度読み直しており、それは私にとってより明確になりました。整数を意味する場合、素数ではないため、値pは必ずしも整数を意味するわけではありませんn。したがって、p実数（つまり、分数）である可能性があります。そして、の全範囲を通過する代わりにn、今では、の全範囲を通過するだけで済みpます。もう1つpはミラーコピーであるため、実際には範囲が半分になります。そして今、私たちは実際にやり直しを続けて、範囲のさらに半分まで square rootそれを行うことができることを確認しています。p

于 2018-09-03T02:38:18.220 に答える
2

合成数は素数の積です。

としましょうn = p1 * p2、どこでp2 > p1、それらは素数です。

その場合n % p1 === 0、nは合成数です。

それならn % p2 === 0、何も推測しn % p1 === 0てください！

n % p2 === 0ですから、それn % p1 !== 0を同時に行う方法はありません。言い換えると、合成数nをp2、p3 ... pi （より大きな係数）で均等に除算できる 場合は、最小の係数p1でも除算する必要があります。最も低い要因p1 <= Math.square(n)は常に真であることがわかります。

于 2018-12-18T09:52:58.210 に答える
2

はい、上で適切に説明したように、数の平方根のMath.floorまで反復して、その素数性をチェックするだけで十分です（sqrt除算のすべての可能なケースをカバーするMath.floorため、および、上記の整数sqrtはすでにその範囲を超えているため）。

これは、このアプローチの単純な実装を表す実行可能なJavaScriptコードスニペットです。その「実行時の使いやすさ」は、かなり大きな数を処理するのに十分です（10 ** 12までの素数と素数ではない両方をチェックしてみました。つまり、1兆、素数のオンラインデータベースと結果を比較し、私の安い電話でもエラーやラグは発生しませんでした）：

function isPrime(num) {
  if (num % 2 === 0 || num < 3 || !Number.isSafeInteger(num)) {
    return num === 2;
  } else {
    const sqrt = Math.floor(Math.sqrt(num));
    for (let i = 3; i <= sqrt; i += 2) {
      if (num % i === 0) return false;
    }
    return true;
  }
}
<label for="inp">Enter a number and click "Check!":</label><br>
<input type="number" id="inp"></input>
<button onclick="alert(isPrime(+document.getElementById('inp').value) ? 'Prime' : 'Not prime')" type="button">Check!</button>

于 2021-02-16T13:57:30.857 に答える
1

数nの素数性をテストするには、最初に次のようなループが必要です。

bool isPrime = true;
for(int i = 2; i < n; i++){
    if(n%i == 0){
        isPrime = false;
        break;
    }
}

上記のループは次のようになります。指定された1<i<nに対して、n / iが整数であるかどうかをチェックします（余りは0のままにします）。n / iが整数であるiが存在する場合、nが素数ではないことを確認でき、その時点でループが終了します。iがない場合、n / iは整数であり、nは素数です。

すべてのアルゴリズムと同様に、次のように質問します。

上記のループで何が起こっているかを見てみましょう。

iのシーケンスは次のようになります：i = 2、3、4、...、n-1

そして、整数チェックのシーケンスは次のようになります：j = n / i、つまりn / 2、n / 3、n / 4、...、n /（n-1）

一部のi=aの場合、n / aは整数であり、n / a = k（整数）

またはn=ak、明らかにn> k> 1（k = 1の場合、a = nですが、iはn​​に到達しません。k= nの場合、a = 1ですが、iは2から始まります）

また、n / k = aであり、前述のように、aはiの値であるため、n>a>1です。

したがって、aとkは両方とも1からnまでの整数（排他的）です。以来、iはその範囲内のすべての整数に到達するため、ある反復ではi = aであり、他の反復ではi=kです。nの素数性テストがmin（a、k）で失敗した場合、max（a、k）でも失敗します。したがって、min（a、k）= max（a、k）（2つのチェックが1つに減る）、つまりa = k、その時点でa * a = nでない限り、これら2つのケースの1つだけをチェックする必要があります。 a = sqrt（n）を意味します。

言い換えると、nの素数性テストがi> = sqrt（n）（つまり、max（a、k））で失敗した場合、i <= n（つまり、min（a）でも失敗します。 、k））。したがって、i = 2からsqrt（n）のテストを実行すれば十分です。

于 2017-06-29T17:43:44.837 に答える