素数かどうかを判断するために素数の平方根まで調べるのはなぜでしょうか?

StackOverflow https://stackoverflow.com/questions/5811151

質問

数値が素数かどうかをテストするには、なぜその数値の平方根までしか割り切れないかどうかをテストする必要があるのでしょうか?

役に立ちましたか？

解決

番号の場合 n 素数ではありません、それは2つの要因に因数分解できます a と b:

n = a * b

両方の場合 a と b の平方根よりも大きかった n, 、 それから a * b より大きいでしょう n. 。したがって、これらの要因の少なくとも1つは、の平方根以下でなければなりません n, 、そして、平方根以下の要因が見つからない場合、 n プライムでなければなりません。

他のヒント

まあ言ってみれば m = sqrt(n) それから m × m = n. 。今if n その時は素数ではありません n と書くことができます n = a × b, 、 それで m × m = a × b. 。それに注意してください m 一方、実際の数です n, a と b 自然数です。

現在、3つのケースがあります。

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

3つのケースすべてで、 min(a, b) ≤ m. 。したがって、tillを検索する場合 m, 、私たちは少なくとも1つの要因を見つけるに違いありません n, 、それを示すのに十分です n プライムではありません。

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

より直感的な説明は次のとおりです。-

100の平方根は10です。Aとbのさまざまなペアについて、AXB = 100としましょう。

a == bの場合、それらは等しく、正確に100の平方根です。 10です。

それらの1つが10未満の場合、もう1つは大きくなければなりません。たとえば、5 x 20 == 100。1つは10を超え、もう1つは10未満です。

AXBについて考えると、そのうちの1つがダウンした場合、もう1つが補償するために大きくなる必要があるため、製品は100にとどまります。

101の平方根は約10.049875621です。したがって、原始性について101番をテストしている場合、10を含む10から10までの整数を試してみる必要があります。プライム。

10を超える数字の1つを持つ一対の要因がある場合、ペアのもう1つは10未満でなければならないため、小さいものが存在しない場合、101の大きな係数はありません。

121をテストしている場合、平方根は11です。プライム整数1〜11（包括的）をテストして、均等に入るかどうかを確認する必要があります。 11は11回になるため、121は素数ではありません。 10時に停止していて、テストされていなかった場合、11を逃したでしょう。

奇数のみをテストしていると仮定して、すべてのプライム整数が2を超えるが、平方根以下をテストする必要があります。

`

仮定する 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つが見つかります。

それはすべて、実際には、因数分解と正方形の根の基本的な使用です。

それは抽象的であるように見えるかもしれませんが、実際には、それは単に、非プライム番号の最大の要因がその平方根でなければならないという事実にあります。

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;
}

与えられた整数と仮定しましょう N プライムではありません、

次に、nを2つの要因に考慮することができます a と b , 2 <= a, b < N そのような N = a*b。明らかに、両方とも大きくすることはできません sqrt(N) 同時に。

一般性を失うことなく、それを想定しましょう a 小さいです。

今、あなたがの除数を見つけることができなかったなら N 範囲内に属します [2, sqrt(N)], 、 どういう意味ですか？

この意味は N 除数はありません [2, a] なので a <= sqrt(N).

したがって、 a = 1 と b = n それゆえ 定義により、 N プライムです.

...

満足していない場合はさらに読みます：

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

（a1, 、b1）、（a2, 、b2）、（a3, 、b3）、.....、（ak, 、bk）。一般性を失うことなく、a私 <b私, 1<= i <=k.

今、それを示すことができるようになります N プライムではありません。私 さらに考慮することができます。そして、私たちはそれを知っています私 <= sqrt(N) したがって、あなたはティルまでチェックする必要があります sqrt(N) すべてをカバーします私. 。したがって、あなたは N プライムです。

...

したがって、数値nがプライムかどうかを確認してください。 nが数字<= sqroot（n）で割り切れるかどうかのみを確認する必要があります。これは、nを任意の2つの要因にfacterるら、xとy、すなわちと言う場合です。 n = xY. xとyのそれぞれは、sqroot（n）未満にすることはできません。y <n xとyのそれぞれはsqroot（n）より大きくすることはできません。x*y> n

したがって、1つの因子はSQROOT（N）以下でなければなりません（他の因子はSQROOT（N）以上です）。したがって、nがプライムかどうかを確認するには、それらの数値を確認する必要があります<= sqroot（n）。

数字「A」があるとしましょう。これは素数ではない[プライム/コンポジット数は平均ではありません。これは、1以外の数値以外の数値で均等に分割できる数字です。たとえば、6は2、または3、ならびに1または6で均等に分割できます。

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

したがって、「A」がプライムでない場合、それは他の2つの数字で分割でき、それらの数値が「B」と「C」であるとしましょう。それは意味します

a = b*c。

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

したがって、「b」＆ "c"は常に<= "a"の平方根です。式 "a = b*c"を証明します。

上記の理由により、数字がプライムかどうかをテストする場合、その数の平方根までのみ確認します。

nを非プライムとします。したがって、少なくとも2つの整数因子が1を超えています。FをNのそのような因子の最小とします。 f> sqrt nと仮定します。 N/Fは整数LTE SQRT Nであるため、Fよりも小さくなります。したがって、FはNの最小因子になることはできません。 Reductio ad Audissum; nの最小因子は、LTE SQRT nでなければなりません。

任意の番号が与えられます n, 、その要因を見つける1つの方法は、その平方根を取得することです p:

sqrt(n) = p

もちろん、乗算する場合 p それ自体が戻ってきます n:

p*p = n

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

a*b = n

どこ p = a = b. 。もしも a その後、増加します b 維持するために減少します a*b = n. 。したがって、 p 上限です。

数字の原始性をテストするには、 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はプライム番号ではないことを確認できます。その時点でループが終了します。 no iの場合、n/iが整数である場合、nはプライムです。

すべてのアルゴリズムと同様に、次のように尋ねます。 もっと良くできますか？

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

I Goesのシーケンス：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ですが、nに到達することはありません。そしてk = nの場合、a = 1ですが、フォーム2を開始します）

また、n/k = a、および上記のように、aはi so n> a> 1の値です。

したがって、AとKは両方とも1とN（排他的）の間の整数です。なぜなら、私はその範囲のすべての整数に到達し、いくつかの反復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（ie、min（a）でも失敗します（a 、k））。したがって、i = 2のテストをSQRT（n）のテストを実行すると十分です。

合成数はすべて素数の積です。

言ってみましょう 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) は常に真実です。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top