C言語　素数判定のコード、総当りを避ける方法

C言語でアルゴリズムを勉強しています。

下記のコードのアルゴリズムについて質問です。
while (i <= nb / i)の部分が理解できません。
なぜこの書き方で総当りを避けられるのでしょうか。
エラトステネスの篩を使った方法ならわかるのですが、なぜ下記の書き方ができるのか、根拠を知りたいです。
ご存知の方がいらっしゃいましたら、教えてください。

c
1int	ft_is_prime(int nb)
2{
3	int	i;
4
5	i = 2;
6	if (nb <= 1)
7		return (0);
8
9　// ここ！
10	while (i <= nb / i)
11	{
12		if (nb % i == 0)
13			return (0);
14		i++;
15	}
16	return (1);
17}

行動規範の内容に同意します

回答4件

ベストアンサー

A = B * Cのように2つの数の積で表されるとしたら、片方は√A以下となります（√Aより大きなものを2つ掛ければ、Aを越えます）。

i <= nb / iを変形すると、i * i <= nbとなります。CPUの処理はわり算より掛け算のほうが早いので、i * i <= nbのまま使ったほうがいいでしょう。

投稿2020/03/19 04:50

maisumakun

総合スコア145201

Bearded-Ockham

2020/03/20 05:00

わざわざ割り算を使っているのは無限ループを避けるためだと思います。説明を簡単にするため、intが8ビットの符号付き整数だとします。例えばnbに127を与えると、i==11ではi*iは121なので次の繰り返しにいきまはすが、i==12だとi*iは144になり、8ビットの符号付では負数となってしまいます。

行動規範の内容に同意します

こう書き直したらわかりませんか？

for(int i = 2; i * i <= nb; i++)
  if (nb % i == 0) return false;
return true;

101が素数かどうかは10以下の数で割れるかだけ調べればいいんですね

余談ですが、素数判定、微々たる差だけど、こうすると1/3で判定が終わるんで好きですね

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

投稿2020/03/19 04:50