結果
問題 | No.106 素数が嫌い!2 |
ユーザー |
|
提出日時 | 2014-12-18 23:46:58 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 35 ms / 5,000 ms |
コード長 | 936 bytes |
コンパイル時間 | 516 ms |
コンパイル使用メモリ | 56,000 KB |
実行使用メモリ | 13,824 KB |
最終ジャッジ日時 | 2024-06-12 01:21:15 |
合計ジャッジ時間 | 1,717 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
#include<iostream> #include<cstring> using namespace std; const int PRIME = 2000005; int nPrime, prime[PRIME]; void makePrime() { static bool isPrime[PRIME]; for (int i = 0; i < PRIME; ++i) isPrime[i] = true; for (int i = 2; i * i < PRIME; ++i) if (isPrime[i]) for (int j = i * 2; j < PRIME; j += i) isPrime[j] = false; nPrime = 0; for (int i = 2; i < PRIME; ++i) if (isPrime[i]) prime[nPrime++] = i; } int N, K; void read() { cin >> N >> K; } void work() { static int cnt[PRIME]; memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < nPrime; ++i) for (int j = prime[i]; j < PRIME; j += prime[i]) ++cnt[j]; int ans = 0; for (int i = 0; i <= N; ++i) if (cnt[i] >= K) ++ans; cout << ans << endl; } int main() { makePrime(); read(); work(); return 0; }