結果

問題 No.12 限定された素数
コンテスト
ユーザー warashi
提出日時 2015-02-13 12:08:06
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,358 bytes
コンパイル時間 148 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 238,304 KB
最終ジャッジ日時 2024-06-23 19:49:37
合計ジャッジ時間 83,597 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
import operator
from collections import defaultdict
from functools import lru_cache, reduce
from itertools import dropwhile, takewhile


def sqrt_floor(n):
    l = 5 * n
    r = 5
    sqrt = 0
    while l > r:
        sqrt += 1
        l = l - r
        r += 10
    return sqrt


def sieve_of_eratosthenes(max):
    is_prime = [True] * (max + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, sqrt_floor(max) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * i, max + 1, i):
            is_prime[j] = False
    return filter(lambda x: is_prime[x], range(max + 1))


def set_of_nums(n):
    return frozenset(list(str(n)))

PRIME = [1] + list(sieve_of_eratosthenes(5000000))
PRIME_NUMS = tuple(map(set_of_nums, PRIME))
N = int(input())
A = frozenset(input().split())
maxdistance = -1
count = 0
now = set()
from_one = True
for i in range(len(PRIME_NUMS)):
    if PRIME_NUMS[i] <= A:
        now.update(PRIME_NUMS[i])
        count += 1
        continue
    if now == A:
        maxdistance = max(maxdistance, PRIME[i] - PRIME[i - count - 1] - 2)
    count = 0
    now = set()
    from_one = False
if now == A:
    if from_one:
        maxdistance = max(maxdistance, 5000000 - 1)
    else:
        maxdistance = max(maxdistance, 5000000 - PRIME[i - count - 1] - 2)
print(maxdistance)
0