エラトステネスの篩について

エラトステネスの篩についての話です。
きっかけは、paizaラーニングのレベルアップ問題集「素数メニュー」からの出題でした。
paiza.jp

整数 N が約数であるかを判定する方法として、エラトステネスの篩という方法があります。
これは 0 以上 N 以下の全ての数について次の手順で素数判定を行う方法です。
エラトステネスの篩とは、Wikipediaによれば...
>エラトステネスの篩は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。
>古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がついている。
と言う、いにしえの篩法で、たしか中学入試の過去問なんかでも見たことがあったような記憶があります。
どこだっけ？
たしかユークリッドの互除法が有効な問題だったような記憶があるけれど...
忘れちゃいました。
そこで僕個人の感想になってしまうけれど、中学入試の過去問（算数）の難度について、いつも思うことがあります。
開成とかラ・サールとかの過去問は、よく出来ているなーと思うと同時に、確信的に解き進められて、しかも解き終えた後に手応えのようなものが感じられることが多いです。
でも灘の過去問は、解きながら不安や迷いが生じてくるとゆーか、解き終えても答え合わせをするまでは、なかなか確信を得られないような出題が多いように感じられています。
まず仮定をおく必要があったり、推論に推論を重ねたり、計算結果が他校の過去問では見かけないような値だったりと、そうゆう傾向とゆーか、まるで試されているように思えてなりません。
だから、日本国内の「中学入試の算数で、一番難しいのはどこかなー？」って、イメージすると、僕の場合は感覚的に灘が思い浮かぶのだけれど、どうなのでしょう。
つまりは、そうやって篩にかけているってことか。

そして、paizaラーニングのレベルアップ問題集「素数メニュー」では、「整数 N が与えられるので、エラトステネスの篩を用いて N が素数かどうかを判定する」という出題でした。

僕が作成、提出したコードは、以下のとおりです。

・エラトステネスの篩

/*
C++による「素数メニュー」問題集
エラトステネスの篩
https://paiza.jp/works/mondai
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<bool> is_prime;
    is_prime.resize(n+1,true);
    is_prime[0]=false;
    is_prime[1]=false;
    for(int i=2;i<=n;i++){
        if(is_prime[i]==true){
            for(int j=2;i*j<=n;j++){
                is_prime[i*j]=false;
            }
        }
    }
    for(int i=0;i<n+1;i++){
        if(is_prime[i]==true){
            if(i==n){
                cout<<"YES"<<endl;
                return 0;
            }
        }
    }
    cout<<"NO"<<endl;
}

ちなみに中学入試の過去問は、受験までやることがないからやっているだけで、志望校とは別です。

paizaラーニングのレベルアップ問題集については、ユーザー同士で解答を教え合ったり、コードを公開したりするのは自由としています。
また授業や研修、教材などにも利用できるそうです。

あと関係ないけれど、「略し方」について、ふと気づいたことがあります。
オンラインゲームでボイスチャットしていると...
女子は、「ボイチャ」と言う。
男子は、「VC」と言う。
次に...
女子は、「パソコン」と言う。
男子は、「PC」と言う。
あとは...
女子は、「ギガタブ」と言う。
男子は、「chrome」と言う。
僕の周りだけかもしれないけれど、こんな感じの傾向があります。
で、僕の場合は「いかに伝わるように話すべきか」で苦心しているから、基本的には略しません。
あっ、でもゲームだと、「デカポ」とか「ビクロイ」とかフツーに言っちゃってるわー。
はい、『フォートナイト』の話でした。