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
| '''
Author: NEFU AB-IN
Date: 2024-07-02 15:26:51
FilePath: \LeetCode\3115\3115.py
LastEditTime: 2024-07-02 15:42:16
'''
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, fabs, floor, gcd, log, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin, stdout
from typing import Any, Dict, Generic, List, TypeVar, Union
TYPE = TypeVar('TYPE')
class SA(Generic[TYPE]):
def __init__(self, x: TYPE, y: TYPE):
self.x = x
self.y = y
def __lt__(self, other: 'SA[TYPE]') -> bool:
return self.x < other.x
def __eq__(self, other: 'SA[TYPE]') -> bool:
return self.x == other.x and self.y == other.y
def __repr__(self) -> str:
return f'SA(x={self.x}, y={self.y})'
N = int(1e2 + 10)
M = int(20)
INF = int(2e9)
OFFSET = int(100)
setrecursionlimit(INF)
def input(): return stdin.readline().rstrip("\r\n")
def read(): return map(int, input().split())
def read_list(): return list(read())
class std:
letter_to_num = staticmethod(lambda x: ord(x.upper()) - 65)
num_to_letter = staticmethod(lambda x: ascii_uppercase[x])
array = staticmethod(lambda x=0, size=N: [x] * size)
array2d = staticmethod(lambda x=0, rows=N, cols=M: [std.array(x, cols) for _ in range(rows)])
max = staticmethod(lambda a, b: a if a > b else b)
min = staticmethod(lambda a, b: a if a < b else b)
removeprefix = staticmethod(lambda s, prefix: s[len(prefix):] if s.startswith(prefix) else s)
removesuffix = staticmethod(lambda s, suffix: s[:-len(suffix)] if s.endswith(suffix) else s)
@staticmethod
def find(container: Union[List[TYPE], str], value: TYPE):
"""Returns the index of value in container or -1 if value is not found."""
if isinstance(container, list):
try:
return container.index(value)
except ValueError:
return -1
elif isinstance(container, str):
return container.find(value)
@staticmethod
def pairwise(iterable):
"""Return successive overlapping pairs taken from the input iterable."""
a, b = tee(iterable)
next(b, None)
return zip(a, b)
class Solution:
def maximumPrimeDifference(self, nums: List[int]) -> int:
primes = []
cnt = 0
is_prime = std.array(1, N)
def prime_filter():
nonlocal primes, cnt, is_prime
is_prime[0] = is_prime[1] = 0
for i in range(2, N):
if is_prime[i]:
primes.append(i)
cnt += 1
j = 0
while j <= cnt and primes[j] * i < N:
is_prime[primes[j] * i] = 0
if i % primes[j] == 0:
break
j += 1
return
prime_filter()
n = len(nums)
i, j = 0, n - 1
while i < n and not is_prime[nums[i]]:
i += 1
while j > 0 and not is_prime[nums[j]]:
j -= 1
return j - i
|