結果

問題 No.12 限定された素数
ユーザー warashiwarashi
提出日時 2015-02-13 12:08:06
言語 Python3
(3.11.6 + numpy 1.26.0 + scipy 1.11.3)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,358 bytes
コンパイル時間 97 ms
コンパイル使用メモリ 11,112 KB
実行使用メモリ 236,004 KB
最終ジャッジ日時 2023-09-06 00:43:52
合計ジャッジ時間 74,259 ms
ジャッジサーバーID
(参考情報)
judge11 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,614 ms
235,956 KB
testcase_01 AC 2,620 ms
235,892 KB
testcase_02 AC 2,630 ms
235,908 KB
testcase_03 AC 2,682 ms
235,888 KB
testcase_04 AC 2,628 ms
235,888 KB
testcase_05 AC 2,646 ms
235,888 KB
testcase_06 AC 2,639 ms
235,844 KB
testcase_07 AC 2,632 ms
235,956 KB
testcase_08 AC 2,666 ms
235,908 KB
testcase_09 AC 2,588 ms
235,904 KB
testcase_10 AC 2,644 ms
235,980 KB
testcase_11 AC 2,669 ms
235,944 KB
testcase_12 AC 2,626 ms
235,944 KB
testcase_13 AC 2,695 ms
235,824 KB
testcase_14 AC 2,676 ms
235,844 KB
testcase_15 AC 2,613 ms
235,888 KB
testcase_16 AC 2,617 ms
235,812 KB
testcase_17 AC 2,579 ms
235,812 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 2,670 ms
235,904 KB
testcase_21 AC 2,702 ms
235,840 KB
testcase_22 AC 2,694 ms
235,956 KB
testcase_23 AC 2,707 ms
235,848 KB
testcase_24 AC 2,635 ms
235,844 KB
testcase_25 AC 2,618 ms
236,004 KB
権限があれば一括ダウンロードができます

ソースコード

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