FUNCoder-第6回活動
第6回活動 2024/06/12 18:15~19:45 @593教室
トップページはこちら: FUNCoder
#2024-06-12
/icons/hr.icon
素数判定について学習します
$ O(N)解法
code:Python
def is_prime(n: int) -> bool:
is_flag = True # N が素数であるかどうかのフラグ
for i in range(2, n):
if n % i == 0:
is_flag = False
break
return is_flag
for i in range(1, 101):
if is_prime(i):
print(f"{i} は素数です。")
else:
print(f"{i} は素数ではありません。")
上記の場合では$ N \leq 10^8くらいまでしか通りません。
しかし、一般的な素数判定の問題は$ N \leq 10^{12}くらいまで与えられます。
$ 10^{12}は無理でも$ \sqrt{10^{12}} = 10^6くらいなら解けるのでは？
つまり、$ O(\sqrt{N})解法を考えてみる必要があります。
$ N = 36の場合について考える
$ 36の約数を列挙すると、$ 1,2,3,4,6,9,12,18,36で割とあります
$ 36 \div 1 = 36
$ 36 \div 2 = 18
$ 36 \div 3 = 12
$ 36 \div 4 = 9
$ 36 \div 6 = 6
$ 36 \div 9 = 4
$ 36 \div 12 = 3
$ 36 \div 18 = 2
$ 36 \div 36 = 1
$ \dfrac{N}{i} = Kが成り立つ時、$ \dfrac{N}{K} = iが成り立ちます。
$ N = iK
$ i \leq Kと仮定すると
$ N = iK \geq i \times i = i^2
$ i^2 \leq N
$ -\sqrt{N} \leq i \leq \sqrt{N}
$ iは自然数なので$ i \leq \sqrt{N}を試せば良い
$ O(\sqrt{N})解法
code:Python
from math import sqrt
# O(√N)
def is_prime(n: int) -> bool:
is_flag = True # N が素数であるかどうかのフラグ
for i in range(2, int(sqrt(N)) + 100):
if n % i == 0:
is_flag = False
break
return is_flag
N = int(input())
if is_prime(N):
print(f"{N} is prime.")
else:
print(f"{N} is not prime.")
int(N**0.5) + 1でも出来ます
(mathライブラリを書くのが面倒なので)
code:Python
# O(√N)
def is_prime(n: int) -> bool:
is_flag = True # N が素数であるかどうかのフラグ
for i in range(2, int(N**0.5) + 1):
if n % i == 0:
is_flag = False
break
return is_flag
N = int(input())
if is_prime(N):
print(f"{N} is prime.")
else:
print(f"{N} is not prime.")
BFS を練習しましょう
code:Python
from collections import deque
H, W = map(int, input().split())
sy, sx = map(lambda x: int(x) - 1, input().split())
gy, gx = map(lambda x: int(x) - 1, input().split())
S = input() for _ in range(H)
q = deque()
# distij := マス(i, j) に辿り着ける最短距離
dist = [-1*W for _ in range(H)]
distsysx = 0
q.append((sy, sx))
d = ((1, 0), (-1, 0), (0, 1), (0, -1))
while q:
now_y, now_x = q.popleft()
for dy, dx in d:
next_y = now_y + dy
next_x = now_x + dx
if not (0 <= next_y < H and 0 <= next_x < W):
continue
if Snext_ynext_x == "#":
continue
if distnext_ynext_x != -1:
continue
distnext_ynext_x = distnow_ynow_x + 1
q.append((next_y, next_x))
# print(*dist,sep="\n")
print(distgygx)