[백준] 1929 소수 구하기 파이썬 풀이 (기본수학2)

코드

x, y = map(int, input().split())

for i in range(x, y+1):
    if i == 1: #1은 소수가 아뉘지!
        continue
    for j in range(2, int(i** 0.5)+1 ):
        if i%j==0:
            break
    else:
        print(i)

풀이

소수는 자신과 1밖에 약수가 없는 수이다.

그럼 모든 수를 돌면서 나누어 떨어지는 수가 있는지 없는지 보면 된다!

그런데 꼭 모든 수를 봐야할까!

해당 수의 제곱근까지만 나눠보면 된다.

약수는 대칭으로 이루어져있기 때문에

(예) 12의 약수는 1 2 3 4 6 12 / 1*12 , 2*6, 3*4 로 대칭

25의 약수는 1 5 25 / 1*25 , 5*5 로 대칭

제곱근 보다 같거나 작은 수까지만 나눠보고 나누어 떨어지는게 있냐 없냐 확인하면 된다