結果

問題 No.3127 Multiple of Twin Prime
コンテスト
ユーザー magurofly
提出日時 2025-04-25 21:46:41
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 191 ms / 2,500 ms
コード長 3,003 bytes
コンパイル時間 29,981 ms
コンパイル使用メモリ 397,656 KB
実行使用メモリ 37,340 KB
最終ジャッジ日時 2025-04-25 21:47:19
合計ジャッジ時間 16,569 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn main() {
    input! {
        t: usize,
        n: [usize; t],
    }

    let mut products = vec![];
    let sieve = LinearSieve::new(10_000_000);

    for pq in sieve.primes().windows(2) {
        let p = pq[0];
        let q = pq[1];
        if p + 2 == q {
            products.push(p * q);
        }
    }

    for n in n {
        let k = products.partition_point(|&x| x <= n );
        if k == 0 {
            println!("-1");
        } else {
            println!("{}", products[k - 1]);
        }
    }
}

use proconio::*;
use primes::*;
pub mod primes {
  // Last Update: 2025-01-12 18:20
  type N = usize;
  
  pub struct LinearSieve { limit: usize, primes: Vec<usize>, table: Vec<usize> }
  impl LinearSieve {
    const REM: [usize; 8] = [1, 7, 11, 13, 17, 19, 23, 29];
    const IDX: [usize; 30] = [8, 0, 8, 8, 8, 8, 8, 1, 8, 8, 8, 2, 8, 3, 8, 8, 8, 4, 8, 5, 8, 8, 8, 6, 8, 8, 8, 8, 8, 7];
    
    pub fn new(limit: N) -> Self {
      let limit: usize = cast(limit);
      let mut table = vec![1; (limit + 29) / 30 * 8 + 1];
      let mut primes = Vec::with_capacity(32);
      for i in 1 .. table.len() {
        let n = 30 * (i >> 3) + Self::REM[i & 7];
        if table[i] == 1 {
          table[i] = n;
          primes.push(n);
        }
        for &p in &primes {
          if n * p > limit || p > table[i] {
            break;
          }
          table[n * p / 30 << 3 | Self::IDX[n * p % 30]] = p;
        }
      }
      Self { limit, table, primes }
    }
    
    pub fn is_prime(&self, n: N) -> bool {
      let n: usize = cast(n);
      assert!(n <= self.limit);
      n == 2 || n == 3 || n == 5 || n % 2 != 0 && n % 3 != 0 && n % 5 != 0 && self.table[Self::index(n)] == n
    }
    
    pub fn primes(&self) -> Vec<N> { [2, 3, 5].into_iter().chain(self.primes.iter().map(|&n| cast(n) )).collect::<Vec<_>>() }
    
    pub fn least_prime_factor(&self, n: N) -> N {
      let n: usize = cast(n);
      assert!(n <= self.limit);
      if n % 2 == 0 { return 2; }
      if n % 3 == 0 { return 3; }
      if n % 5 == 0 { return 5; }
      cast(self.table[Self::index(n)])
    }
    
    pub fn prime_division(&self, n: N) -> Vec<N> {
      let mut n: usize = cast(n);
      assert!(n <= self.limit);
      let mut divisors = vec![];
      while n > 1 {
        let d = self.least_prime_factor(n);
        n /= d;
        divisors.push(cast(d));
      }
      divisors
    }
    
    pub fn prime_division_pairs(&self, n: N) -> Vec<(N, usize)> {
      if n == 1 {
        return vec![];
      }
      let pd = self.prime_division(n);
      let mut prev_p = pd[0];
      let mut e = 0;
      let mut pairs = vec![];
      for p in pd.into_iter().chain(Some(1)) {
        if p == prev_p {
          e += 1;
        } else {
          pairs.push((prev_p, e));
          
          prev_p = p;
          e = 1;
        }
      }
      pairs
    }
    
    fn index(n: usize) -> usize { n / 30 << 3 | Self::IDX[n % 30] }
  }
  
  fn cast(n: impl Into<usize>) -> usize { n.into() }
}
0