[백준] 1929번 - 소수 구하기 파이썬 풀이

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

1929번 - 소수 구하기

🐢 풀이

 

소수를 구하는 문제를 구현하는 것은 어렵지 않으나 코딩테스트에서는 시간초과되기 싶다. 그래서 이번 문제는 에라토스테네스의 체를 먼저 접근해보자. 에라토스테네스의 체란 일정 범위 내에 수열에서 배수들을 제거해 소수만 걸러내는 체를 뜻한다. 예시 코드를 먼저 보자.

M, N = map(int,input().split())

for i in range(2, int(N**0.5)+1):
	if turtle[i] == True:
		for j in range(i*2, N+1, i):
			turtle[j] = False

백준문제에서 나온 예시값처럼 위 코드에서 입력값 M과 N에 각각 3, 16을 넣었다는 가정하에 진행하면

i = 2 일 때, 4부터 2씩 증가하며 False한다.

3	4	5	6
7	8	9	10
11	12	13	14
15	16

i = 3 일 때, 6부터 3씩 증가하며 False한다.

3	4	5	6
7	8	9	10
11	12	13	14
15	16

i = 4 일 때, 8부터 4씩 증가하며 False한다.

3	4	5	6
7	8	9	10
11	12	13	14
15	16

위 표에서 볼 수 있듯이 False처리되지 않은 것은 3, 5, 7, 11, 13이다. 이 값만이 소수임을 확인할 수 있다.

 

🐢최종 코드

M, N =map(int,input().split())

for i in range(M, N+1):
    if i == 1: # 1은 소수 아님
        continue
    for j in range(2, int(i**0.5)+1):
      if i % j == 0: # 약수가 존재하는지 확인
        break   # 약수 존재한다면 break로 멈춤
    else:
      print(i)

에라토스테네스의 체를 이용하여 푼 최종 코드이다.

 

Don't stop