結果
問題 |
No.2750 Number of Prime Factors
|
ユーザー |
![]() |
提出日時 | 2024-05-26 14:58:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 761 bytes |
コンパイル時間 | 835 ms |
コンパイル使用メモリ | 76,008 KB |
最終ジャッジ日時 | 2025-02-21 16:46:00 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 19 |
ソースコード
#include <iostream> #include <cassert> #include <vector> using namespace std; int f(long long x, const vector<long long> &primes) { int ret = 0; for (long long i: primes) { while (x % i == 0) { ret++; x /= i; } } if (x > 1) ret++; return ret; } int main() { long long M; cin >> M; int N = 1e5 + 1; vector<long long> primes; vector<bool> is_prime(N, true); is_prime[0] = false; is_prime[1] = false; for (int i = 2; i <= N; i++) { if (is_prime[i]) { primes.push_back((long long)i); for (int j = i + i; j <= N; j += i) { is_prime[j] = false; } } } int ret = 0; for (int i = 0; i < N && M >= primes[i] ; i++) { M /= primes[i]; ret++; } cout << ret << endl; return 0; }