[백준 1929번] 소수 구하기 - python

1929번

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

1929번: 소수 구하기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

🐰 나의 코드

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

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

 

 

문제에서는 M 이상 N 이하의 소수를 모두 출력하라고 하고 있다.

우선 M과 N을 입력받은 걸 각각 저장한 후, 소수를 판별해야겠다고 생각했다.

for문을 통해서 m과 n을 전부 하나씩 확인한다. 그러기 위해서는 범위가 m이상 n+1 미만으로 해야 n까지 확인할 수 있다!

for문 안에서는 sum을 통해 소수의 여부를 판단하려고 한다.

만약 i가 1이라면 이중 for문 전에 pass를 해서 넘겨버린다^^ 1은 소수가 아니니까!

1이 아니라면, for문을 통해 소수임을 판별해야 한다.

수의 범위는 제곱근으로 설정하면서 int로 정수화를 시켰고, 1을 더했다.

그래야 제곱근을 포함할 정도라고 생각했기 때문이다!

if문을 통해 만약 제곱근까지의 수를 2에서부터 올리면서 j가 i로 나누었을 때 나머지가 없다면, 해당 수는 소수가 아니다.

따라서 break문을 통해 바로 for문을 빠져 나오게 해서 불필요한 계산을 없앴다.

만약 sum이 계속해서 0이라면, 고대로 i를 프린트하면서 출력시킨다.