#956281 (PyPy3) No.12 限定された素数

• 問題: No.12 限定された素数
• ユーザー: Mao-beta
• 提出日時: 2024-02-29 00:35:28
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 393 ms / 5,000 ms
• コード長: 2,882 bytes
• コンパイル時間: 348 ms
• コンパイル使用メモリ: 82,228 KB
• 実行使用メモリ: 141,428 KB
• 最終ジャッジ日時: 2024-09-29 12:27:51
• 合計ジャッジ時間: 9,645 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
other	AC * 26

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
import sys
import math
import bisect
from heapq import heapify, heappop, heappush
from collections import deque, defaultdict, Counter
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD99 = 998244353
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
SMI = lambda: input().split()
SLI = lambda: list(SMI())
EI = lambda m: [NLI() for _ in range(m)]
# 高速エラストテネス　sieve[n]はnの最小の素因数
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(4, n + 1, 2):
        sieve[i] = 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i * 2):
            if sieve[j] == j:
                sieve[j] = i
    return sieve
prime_table = make_prime_table(5000001)
# 素数列挙
primes = [p for i, p in enumerate(prime_table) if i == p]
# 素因数分解　上のprime_tableと組み合わせて使う
def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        result.append((p, e))
    return result
# Nの素因数分解を辞書で返す(単体)
def prime_fact(n):
    root = int(n**0.5) + 1
    prime_dict = {}
    for i in range(2, root):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict
# 約数列挙（単体）
def divisors(x):
    res = set()
    for i in range(1, int(x**0.5) + 2):
        if x % i == 0:
            res.add(i)
            res.add(x//i)
    return res
def main():
    N = NI()
    A = set(SLI())
    if len(A) == 10:
        print(4999999)
        return
    PN = len(primes)
    ans = -1
    l = 0
    r = 0
    # print(A)
    while l < PN and r < PN:
        S = set()
        r = l
        K = 0
        L = 0
        for i in range(l, PN):
            p = str(primes[i])
            ok = True
            for sp in p:
                if sp not in A:
                    ok = False
            if ok:
                S |= set(list(p))
            else:
                r = i
                break
        if S == A and l < r:
            if l == 0:
                K = 1
            else:
                K = primes[l-1] + 1
            if r == PN:
                L = 5000000
            else:
                L = primes[r] - 1
            ans = max(ans, L-K)
            l = r
        elif l < r:
            l = r
        elif l == r:
            l += 1
    print(ans)
if __name__ == "__main__":
    main()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX