AtCoderログ：0116 - ABC 149 C

問題

問題文

$X$ 以上の素数のうち、最小のものを求めよ。

制約

・$2 \le X \le 10^5$

収録されている問題セット

• AtCoder Problems Boot camp for beginners Easy 100 [#021]

回答

回答1 (AC)

自然数 $x$ が素数であるとは、$x$ が $1$ と $x$ 以外の自然数では割り切れないということです。そこで $x$ に対して $i=2,3,\dots,x-1$ で割り切れるかどうかを確認し、割り切れた場合には $x$ を1増加させる、という戦略が考えられます。コードは以下のようになりました。

abc149c-1.cpp

#include <bits/stdc++.h>
using namespace std;

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

  int i;
  while ( true ) {
    for ( i=2; i<x; i++ ) {
      if ( x%i==0 ) {
        break;
      }
    }
    if ( i==x ) {
      cout << x << endl;
      break;
    }
    x += 1;
  }
}

調べたこと

AtCoder の解説 → ユーザ解説

素数を生成する関数を利用していました。

AtCoder の解説 → コンテスト全体の解説

回答2と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0115 - ABC 116 B