素数判定のプログラムを教えてください…

前提・実現したいこと

C言語で入力した自然数が素数かどうか判断するプログラムを作成したい。

発生している問題・エラーメッセージ

作ろうとしてみたのですが、作り方がさっぱりわかりません。

該当のソースコード

C言語

試したこと

If文の中でさらにIf文を書いてみたが、うまくいかなかった。
フローチャートを自分で作成してみた
入力する数字をpとしてp mod=0というところまではわかるのですが、それ以降がわかりません

補足情報（FW/ツールのバージョンなど）

私はEclipseというアプリで作成しています。

meg_

2020/08/02 07:34

プログラムではなく手計算なら出来ますか？

cateye

2020/08/02 08:00 編集

２よりも大きい素数（3 5 7 11 13 17 ・・・）は全て奇数なのは分かりますか？・・・なので、奇数のみを対象とした判定をしましょう。（入力された数が偶数なら、２以外は素数ではない）入力される数値の最大値は？・・・環境（OSやコンパイラ）によって、処理できる最大値が変わってきます。

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

回答4件

最も簡単で最も遅い実装かな？

C
1#include <stdio.h>
2
3int is_prime(int n)
4{
5	int i = 2;
6	if (n > 1)
7		while (n % i) i++;
8	return i == n;
9}
10
11int main(void)
12{
13	for (int n = 0; n < 100; n++)
14		if (is_prime(n)) printf("%d\n", n);
15}

投稿2020/08/02 17:54

kazuma-s

総合スコア8224

episteme

2020/08/03 00:38

割り切れなかった数を勘定するのか。なるほど、確かに"遅い"わ。 # なんか悔しいぞwww

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

ベストアンサー

2,3,4...n-1 のいずれかで割り切れるnは素数ではないのだから:

C
1// nが素数なら1, 素数でないなら0を返す
2int is_prime(int n) {
3  int i;
4  if ( n < 2 ) return 0; // n < 2 のとき、nは素数ではない(としておこう)
5  for ( i = 2; i < n; ++i ) { // i = 2, 3, 4 ... n-1 に対し
6    if ( n % i == 0 ) { // n が i で割り切れたら
7      return 0; // 素数ではない
8    }
9  }
10  return 1;
11}