結果

問題 No.12 限定された素数
ユーザー vjudge1
提出日時 2025-09-06 08:38:37
言語 Crystal
(1.14.0)
結果
RE  
実行時間 -
コード長 1,272 bytes
コンパイル時間 15,745 ms
コンパイル使用メモリ 308,832 KB
実行使用メモリ 13,640 KB
最終ジャッジ日時 2025-09-06 08:38:57
合計ジャッジ時間 17,546 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 RE * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

M = 5_000_000

n = gets.not_nil!.to_i
a = Array(Int32).new(n) { gets.not_nil!.to_i }

# Track which digits are in input array A
b = Array(Bool).new(10, false)
a.each { |digit| b[digit] = true }

# Sieve of Eratosthenes
is_prime = Array(Bool).new(M + 1, true)
is_prime[0] = is_prime[1] = false

primes = [] of Int32
(2..M).each do |i|
  next unless is_prime[i]
  primes << i
  (2 * i).step(to: M, by: i) { |j| is_prime[j] = false }
end
primes << M + 1 # sentinel

# Helper: extract digits present in a number
def solve(p : Int32)
  res = Array(Bool).new(10, false)
  num = p
  while num > 0
    res[num % 10] = true
    num //= 10
  end
  res
end

now = Array(Bool).new(10, false)
ans = -1
last = 0

(primes.size - 1).times do |i|
  c = solve(primes[i])
  
  # Check if prime contains any digit not in original array A
  flag = false
  10.times do |j|
    if c[j] && !b[j]
      flag = true
      break
    end
  end

  if flag
    # Reset current digit set and update last valid prime start
    now.fill(false)
    last = primes[i]
    next
  end

  # Accumulate digits from this prime
  10.times { |j| now[j] = true if c[j] }

  # Check if accumulated digits match original set
  if b == now
    gap = primes[i + 1] - last - 2
    ans = [ans, gap].max
  end
end

puts ans
0