この日記について

この日記は自分が競技プログラミングに関して学んだ事を積み上げていくために書いていく日記です！
今日から毎日書いていこうと思うので是非みてください

学んだこと

素数判定

素数判定の方法は大きく分けて2つある。具体的な方法としては普通に割り算を行い求める愚直な方法とエラトステネスの篩という少し賢い方法があります！

実装例
単純な方法

 #素数を判定するための関数 
def isPrime(N):
	LIMIT = int(N ** 0.5)
	for i in range(2, LIMIT + 1):
		if N % i == 0:
			return False
	return True

# 入力
Q = int(input())
X = [ None ] * Q
for i in range(Q):
	X[i] = int(ionput()n
# 出力
for i in range(Q):
	Answer = isPrime(X[i])
	if Answer == True:
		print("Yes")
	else:
		print("No") 

コードの解説
このコードの中で一番理解しづらい部分はlimitの部分である。
なぜfor文の実行回数がlimit+1であるというと
すべての合成数は2以上√N以下の約数をもつからである。(N=自然数）
合成数とは素数の反対の意味で自然数の中で1とその数自身以外の約数を持つ数字のことである。
例としては10や4などの普通の数の事。
なぜすべての合成数は2以上√N以下の約数をもつと言う事を背理法を用いて証明する。

lこのような理由からlimitは√Nであれば良い
他の部分は基本的な部分であるので説明は省略

エラトスネスの篩
実装例と解説

まずエラトスネスの篩とは
素数かどうか調べたい数をNまで書き出しまず2の倍数の物を消したら残った物の中で最小値である数の倍数を消すという作業を√N以下までの数を消すまで続けるというものである。
実装例を下に示す

Deleted = [ False ] * 1000009
LIMIT = int(N ** 0.5)
for i in range(2, LIMIT+1):
	if Deleted[i] == False:
		for j in range(i*2, N+1, i):
			Deleted[j] = True
 
# 答えを出力
for i in range(2, N+1):
	if Deleted[i] == False:
		print(i)

詳しい説明を書き加えようと思ったが面倒なので後で記述しようかな？
要望があればかきます！