結果

問題 No.12 限定された素数
ユーザー lam6er
提出日時 2025-03-31 17:48:31
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 896 ms / 5,000 ms
コード長 1,682 bytes
コンパイル時間 251 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 239,780 KB
最終ジャッジ日時 2025-03-31 17:49:42
合計ジャッジ時間 24,100 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect

def main():
    n = int(sys.stdin.readline())
    allowed = set(sys.stdin.readline().split())
    max_limit = 5000000

    # Generate sieve of Eratosthenes up to max_limit
    sieve = [True] * (max_limit + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(max_limit**0.5) + 1):
        if sieve[i]:
            sieve[i*i : max_limit+1 : i] = [False] * len(sieve[i*i : max_limit+1 : i])
    
    primes = [i for i, is_p in enumerate(sieve) if is_p]

    # Determine invalid primes (primes containing digits not in allowed)
    invalid_primes = [0]
    for p in primes:
        s = str(p)
        if any(c not in allowed for c in s):
            invalid_primes.append(p)
    invalid_primes.append(5000001)  # Upper boundary
    invalid_primes = sorted(list(set(invalid_primes)))  # Remove duplicates and sort

    max_LK = -1

    # Iterate through consecutive pairs in invalid_primes to find valid segments
    for i in range(len(invalid_primes) - 1):
        prev = invalid_primes[i]
        next_val = invalid_primes[i + 1]
        start_idx = bisect.bisect_right(primes, prev)
        end_idx = bisect.bisect_left(primes, next_val)
        primes_segment = primes[start_idx:end_idx]

        # Collect all digits used in this segment
        digits_used = set()
        for p in primes_segment:
            digits_used.update(str(p))
        
        # Check if the collected digits exactly match the allowed set
        if digits_used == allowed:
            candidate = next_val - prev - 2
            if candidate > max_LK:
                max_LK = candidate

    print(max_LK if max_LK != -1 else -1)

if __name__ == "__main__":
    main()
0