結果
問題 | No.1661 Sum is Prime (Hard Version) |
ユーザー | akakimidori |
提出日時 | 2021-08-28 21:34:39 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 764 ms / 3,000 ms |
コード長 | 1,085 bytes |
コンパイル時間 | 1,200 ms |
コンパイル使用メモリ | 152,448 KB |
実行使用メモリ | 4,656 KB |
最終ジャッジ日時 | 2023-08-14 03:43:13 |
合計ジャッジ時間 | 8,599 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 454 ms
4,656 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,384 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 1 ms
4,380 KB |
testcase_10 | AC | 0 ms
4,380 KB |
testcase_11 | AC | 1 ms
4,380 KB |
testcase_12 | AC | 354 ms
4,392 KB |
testcase_13 | AC | 331 ms
4,384 KB |
testcase_14 | AC | 438 ms
4,380 KB |
testcase_15 | AC | 611 ms
4,380 KB |
testcase_16 | AC | 462 ms
4,612 KB |
testcase_17 | AC | 393 ms
4,612 KB |
testcase_18 | AC | 140 ms
4,384 KB |
testcase_19 | AC | 277 ms
4,376 KB |
testcase_20 | AC | 147 ms
4,376 KB |
testcase_21 | AC | 389 ms
4,380 KB |
testcase_22 | AC | 764 ms
4,376 KB |
testcase_23 | AC | 750 ms
4,380 KB |
ソースコード
fn prime_count(n: usize) -> usize { if n <= 1 { return 0; } let sqrt = (1..).find(|p| p * p > n).unwrap() - 1; let mut large = vec![0; sqrt + 1]; let mut small = vec![0; sqrt + 1]; for (i, (large, small)) in large.iter_mut().zip(&mut small).enumerate().skip(1) { *large = n / i - 1; *small = i - 1; } for p in 2..=sqrt { if small[p] == small[p - 1] { continue; } let pi = small[p] - 1; let q = p * p; for i in 1..=sqrt.min(n / q) { large[i] -= *large.get(i * p).unwrap_or_else(|| &small[n / (i * p)]) - pi; } for i in (q..=sqrt).rev() { small[i] -= small[i / p] - pi; } } large[1] } fn main() { let mut s = String::new(); std::io::stdin().read_line(&mut s).unwrap(); let a = s.trim().split_whitespace().flat_map(|s| s.parse::<usize>()).collect::<Vec<_>>(); let (l, r) = (a[0], a[1]); let ans = prime_count(r) - prime_count(l - 1) + prime_count(2 * r) - prime_count(2 * l); println!("{}", ans); }