[白俊]1929号:少数を救う

質問する

に感銘を与える

資料構造書には少数の羅列部分があるため,(p 98)は3つの方法で解答した.最終的に、テストステロンを用いた最後の解毒方法はタイムアウトしなかった.正直、この部分は本から読んでもよくわからないので、星を描いてあげましたが、まだ理解していません.

コンセプト

エラトニスのふるい(名前は重要ではないようです)
小数をその小数の平方根以下の整数で割った場合、小数となります.

最初の解

M, N = map(int, input().split())

for i in range(M, N+1):
    for j in range(2, i):
        if i % j == 0:
            break
    else :
        print(i)

第二の解釈

2からn-1までの小数を区別しない特性を利用する
小数をsosuリストに保存し、その小数のみを使用して除算します.

M, N = map(int, input().split())

ptr = 0
sosu = [2]
ptr +=1


for i in range(M, N+1, 2):
    for j in range(len(sosu)):
        if i % sosu[j] == 0:
            break
    else :
        sosu.append(i)
        print(i)

正解を解く

# 소수는 소수의 제곱근까지 나눴을 때 나눠떨어지지 않으면 소수가 됨
M, N = map(int, input().split())

for i in range(M, N+1):
    if i == 1:
        continue # continue는 for문 if문 같은 곳에서 사용 시, 다음 루프로 넘기는 역할을 함
        
    for j in range(2, int(i**0.5)+1):  
    # (2,int(i**0.5)+1, 2)로 하면 2,4 의 경우 2만 출력됨 (3을 건너뛰기 때문)
        if i % j == 0:
            break
    else :
        print(i)