エラトステネスのふるいCプログラム - 私たちはなぜi <= sqrt（n）などを持っていますか？

これはもっと数学的な質問だと思うけど、それはプログラミングに非常に関連しているので、私はそれを撃つだろうと思った。以下はCで素数のリストを計算するためのエラトステネスのふるいを使用してプログラムのための私のコードへのリンクです：エラトステネスのふるいCプログラム - 私たちはなぜi <= sqrt（n）などを持っていますか？

私の質問があり、ループのためのプログラムの冒頭では、なぜ我々は持っていますi < = sqrt（n）およびj < = n/j？これは私の教授が提案したものであり、プログラムの目的のために働いています（配列のメモリ制限を超えないなど）。しかし、なぜそれがうまくいくのか理解していません。

ありがとうございます！

2012-02-14 Joshpho

I <要因の一つは数 – Treesrule14

の任意の因数分解に以下又は数の平方根に等しくなければならないので= SQRT（n）は ' i <= sqrt（n） 'はひどく遅い演算であり、浮動小数点とは何の関係もない演算で浮動小数点を含みます。その代わりに、式を 'i * i <= n'と書くべきです。 –

'i * iの値が分かっているならば、'（i + 1）*（i + 1） 'の値は' i * i + 2 * i + 1'として計算するのが簡単です乗算なしで）。 –

いずれn = a * a、又はn = b * c、b < a < c。したがって、aまたはbのいずれかを見つけるために、までaをチェックする必要があります - a * aの平方根までです。 bが見つかると、c（c = n/b）とわかります。

2012-02-14 06:14:27

（NUM命名）数NUM> SQRT（N）の場合と
numはなければならない素数ではない：NUM = * bの
の一つとしなければならないSQRT（N）
以下B は、それはすでに数の平方根以下の手順（N）
ので、あなたがこの

ようなコードを書くことができ

SQRTの上に数を判断する必要（n）が存在しないの前に減少します

for(j = 2 ; i * j <= n ; j++) 
{ 
    primecap[j * i] = FALSE; 
}

が、それはより多くの理解でなければならない

2012-02-14 08:12:09 fork123x

答えて