からまでの数が素数であるかどうかの配列(素数テーブル)をで構築する。 はじめに まず、このような素数テーブルの構築といえばいわゆるエラトステネスのふるいが有名です。小さい方から、その倍数にバツマークを付けていくと、で構築できます。実装も素直で簡単です: const int N = 10000001; bool prime[N]; void build_sieve(){ fill(prime,prime+N,true); prime[0] = prime[1] = false; for(int i=2; i<N; ++i)if(prime[i]){ for(int j=2*i; j<N; j+=i) prime[j] = false; } } 実装 次にの実装を見てみます。 const int N = 10000001; int mind[N]; vector<int> pr; void b