[백준] 소수 구하기 1929번 파이썬 Python 수학

📌생각해보기

1. 소수는 해당 수를 1과 나누었을 때 나머지가 0이 나오고 해당 수를 자기 자신과 나누어서 나머지가 0이 나오는 수. 딱 "1"과 자기 자신을 나누었을 때만 나머지가 0이 나와야한다.
   3 % 1 = 0
   3 % 2 = 1
   3 % 3 = 0
   -> 3은 소수
   
   9 % 1 = 0
   9 % 2 = 1
   9 % 3 = 0
   9 % 4 = 1
   9 % 5 = 4
   9 % 6 = 3
   9 % 7 = 2
   9 % 8 = 1
   9 % 9 = 0
   -> 9는 "9 % 3 = 0"때문에 소수 아님

2. 약수의 성질을 이용한다.
   모든 약수는 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다.
   예) 16의 약수는 1, 2, 4, 8, 16
   이때 2 x 8 = 16은 8 x 2 = 16과 대칭이다.
   이말은, 16이 2로 나누어 떨어진다는 것은 8로도 나누어 떨어진다는 것이다.
   따라서 16의 약수 중 가운데인 4까지만 확인하면 되므로 16까지 확인하지 않아도 된다.
   

   제곱근(루트) 구하는 방법
   1) x ** 0.5
   2) math.sqrt(x)
   
   

📌내가 작성한 코드

m, n = map(int, input().split())

for i in range(m, n+1):
    if i <= 1:
        continue
    
    for j in range(2, int(i ** 0.5)+1):
        if i % j == 0:
            break
    else:
        print(i)

📌풀이

1. m, n의 입력을 받을 수 있도록 해주고 int로 형변환을 해준다.
   m번부터 n까지 반복문을 돌려준다.

m, n = map(int, input().split())

for i in range(m, n+1):

2. 0, 1은 소수가 아니기 때문에 0, 1이 나오면 continue를 걸어준다.

if i <= 1:
        continue

3. i가 2이상일 때 약수의 성질을 이용해서 2부터 제곱근(루트) + 1까지 반복시킨다.
   만약, i를 2부터 제곱근(루트) + 1까지 나누어서 나머지가 0이면 소수가 아님.
   모두 나머지가 0이 아니면 소수.

for j in range(2, int(i ** 0.5)+1):
    if i % j == 0:
       break
else:
    print(i)