코딩테스트 18일차(2025.02.06) - 백준1929번(소수 구하기)

문제유형

에라토스테네스의 체

풀이 방법 도출 과정

1. 에라토스테네스 체를 사용하는 문제이다.

2. 1은 소수가 아니므로 제외해준다. 

3. 소수 판별을 위한 반복문을 실행한다. 

• 반복범위는 2부터 int(i ** 0.5) + 1까지이다.
• 특정 수의 제곱근까지만 약수를 검사하면, 해당 수의 모든 약수를 판별할 수 있다.

4. 약수가 존재하면 소수가 아니다.

• 만약 i가 j로 나누어떨어진다면, i는 약수를 가지므로 소수가 아니다.
• 그렇지 않다면 i는 소수이다. 

5. 이 방식대로 코드를 작성해보았다.

시간 복잡도

외부 for문은 m에서 n까지 i번 반복하기 때문에 대략 O(n)이며 내부 반복문은 2에서 int(i**0.5)+1개 반복하기 때문에 대략 O(i**0.5)인데 전체 복잡도는 i**0.5를 n번 반복하기 때문에 적분을 사용한다면 O(n**2/3)정도로 대략 O(n)이다.

코드 및 간단설명

에라토스테네스의 체를 사용한 문제로 소수 판별을 위한 판별문을 사용하였다. 

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)

 

[백준] 1929번 : 소수 구하기 (파이썬)

이 사람 풀이를 참조하였다.