素数列挙
説明
エラトステネスの篩および単純な探索。
計算量
O(N1.5)
使い方
primes(n)でnまでの素数を列挙して返す。
必要なライブラリ
- vector
ソースコード
単純探索
vector<int> primes(int n) {
vector<int> p; p.reserve(1.26 * n / log(n)); p.pb(2);
int s = 0, t = 4, f = 0;
for (int i = 3; i < n; i++) {
f = 1; rep(j, s) if (f = i % p[j], !f) break;
if (f) if (t - i) p.pb(i); else t = p[++s] * p[s];
}
return p;
}
エラトステネスの篩
vector<int> primes2(int n) {
vector<int> p; p.reserve(1.26 * n / log(n)); p.pb(2);
int *isd = new int[n]; memset(isd, 0, sizeof(int) * n);
for (int i = 3; i < n; i += 2) if (!isd[i])
{ p.pb(i); for (int j = i * i; j < n; j += i) isd[j] = 1; }
delete [] isd; return p;
}
確認
なし
