[백준] 1963 : 소수경로

문제링크

https://www.acmicpc.net/problem/1963

소수 구하는 법 정리

특정 수가 소수인지 판별

num = 3 # 특정 수

# 2부터 제곱근인 수까지 나눴을 때 한 번도 나누어 떨어지지 않았으면
# c출력하기
for i in range(2, int(num**0.5)+1):
    if num % i == 0:
        break # 나누어 떨어지면 소수가 아닌 것
else :
    print(num) # 한 번도 나누어 떨어진 적 없었으면 소수인 것

M부터 N까지 소수인 것 모두 판별

# 소수는 소수의 제곱근까지 나눴을 때 나눠떨어지지 않으면 소수가 됨
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)