結果

問題 No.12 限定された素数
ユーザー warashiwarashi
提出日時 2015-02-13 12:08:06
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3,037 ms
238,304 KB
testcase_01 AC 3,033 ms
238,172 KB
testcase_02 AC 3,031 ms
238,176 KB
testcase_03 AC 3,079 ms
238,176 KB
testcase_04 AC 3,098 ms
238,172 KB
testcase_05 AC 3,073 ms
238,172 KB
testcase_06 AC 3,070 ms
238,172 KB
testcase_07 AC 3,056 ms
238,176 KB
testcase_08 AC 3,062 ms
238,148 KB
testcase_09 AC 3,024 ms
238,304 KB
testcase_10 AC 3,036 ms
238,172 KB
testcase_11 AC 3,052 ms
238,176 KB
testcase_12 AC 3,122 ms
238,176 KB
testcase_13 AC 3,037 ms
238,172 KB
testcase_14 AC 3,029 ms
238,172 KB
testcase_15 AC 3,089 ms
238,176 KB
testcase_16 AC 3,070 ms
238,044 KB
testcase_17 AC 3,023 ms
238,176 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 2,994 ms
238,180 KB
testcase_21 AC 3,022 ms
238,180 KB
testcase_22 AC 3,040 ms
238,180 KB
testcase_23 AC 3,000 ms
238,176 KB
testcase_24 AC 3,049 ms
238,172 KB
testcase_25 AC 3,048 ms
238,172 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