プログラミング基礎講習会

Appearance

6. 繰り返し処理

6.Q Prime Check（★★☆） ​

問題 ​

正の整数を1つ入力として受け取り、が素数ならPrime、そうでなければNot Primeと出力しよう。

入出力例 ​

例1 ​

入力 ​

Input
17

出力 ​

Output
Prime

例2 ​

入力 ​

Input
21

出力 ​

Output
Not Prime

ヒント ​

ヒント1

からまでの数で割り切れるかを調べると素数判定ができる。

ヒント1

のときを場合分けしておくとプログラムが書きやすい。

解答例 ​

解答例
cpp
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    if (n == 1) {
        cout << "Not Prime" << endl;
        return 0;
    }

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

    if (is_prime) {
        cout << "Prime" << endl;
    }
    else {
        cout << "Not Prime" << endl;
    }
}

割る数をから増やしていき、i*i <= Nを満たす範囲だけ調べれば十分なことも知られている。

cpp
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    if (n == 1) {
        cout << "Not Prime" << endl;
        return 0;
    }

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

    if (is_prime) {
        cout << "Prime" << endl;
    }
    else {
        cout << "Not Prime" << endl;
    }
}