結果
問題 |
No.3127 Multiple of Twin Prime
|
ユーザー |
|
提出日時 | 2025-04-26 09:00:56 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 247 ms / 2,500 ms |
コード長 | 2,051 bytes |
コンパイル時間 | 13,137 ms |
コンパイル使用メモリ | 398,868 KB |
実行使用メモリ | 20,208 KB |
最終ジャッジ日時 | 2025-04-26 09:01:14 |
合計ジャッジ時間 | 16,159 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 12 |
ソースコード
fn main() { input!{ t: usize, } // 素数リスト let primes = prime_list(10_000_000); // p,p+2を満たすpだけを列挙する let pprimes = match_primes(&primes); for _ in 0..t { input!{ n: usize, } // 二分探索で条件を満たすp番目のmaxを調べる let mut ok = -1; let mut ng = pprimes.len() as i32; for _ in 0..50 { let mid = ((ok + ng) / 2) as usize; if pprimes[mid] * (pprimes[mid] + 2) <= n { ok = mid as i32; } else { ng = mid as i32; } } if ok != -1 { println!("{}", pprimes[ok as usize] * (pprimes[ok as usize] + 2)); } else { println!("-1"); } } } // エラトステネスの篩による素数リスト pub fn prime_list(x: usize) -> Vec<usize> { let mut bools = vec![true; x + 1]; bools[0] = false; bools[1] = false; let mut i = 2; while i * i <= x { if bools[i] { let mut now = 2 * i; while now <= x { bools[now] = false; now += i; } } i += 1; } let mut ret = Vec::new(); for i in 0..=x { if bools[i] { ret.push(i) }; } ret } fn match_primes(primes: &Vec<usize>) -> Vec<usize> { let sz = primes.len(); let mut ret = Vec::new(); for i in 0..sz-1 { if primes[i+1] - primes[i] == 2 { ret.push(primes[i]); } } ret } // const MOD17: usize = 1000000007; // const MOD93: usize = 998244353; // const INF: usize = 1 << 60; // let dx = vec![!0, 0, 1, 0]; // 上左下右 // let dy = vec![0, !0, 0, 1]; // 上左下右 // let d = vec!{(!0, 0), (0, !0), (1, 0), (0, 1)}; // 上左下右 #[allow(unused)] use proconio::{input, marker::Chars, marker::Usize1}; #[allow(unused)] use std::{ mem::swap, cmp::min, cmp::max, cmp::Reverse, collections::HashSet, collections::BTreeSet, collections::HashMap, collections::BTreeMap, collections::BinaryHeap, collections::VecDeque, iter::FromIterator, }; // 配列のスペース区切り出力 #[allow(unused)] fn vec_print<T: std::fmt::Display>(vec: &Vec<T>) { let sz = vec.len(); for i in 0..sz-1 { print!("{} ", vec[i]); } println!("{}", vec[sz-1]); }