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

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

1929번: 소수 구하기

 

수학 파트를 훑을 예정이다. 머리식힐겸 옛날 수학 공식도 상기시킬겸..

 

단순히 순서대로 보면서 cnt가 증가하면 출력제외 0이면 출력하게 짯다.

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

for i in range(m, n+1):
    cnt = 0
    for j in range(2, i):
        if i % j == 0:
            cnt+=1
    if cnt == 0:
        print(i)

 

완성을 했는데 시간초과 떳다;

 

에라토스테네스 체로 작성해야되는 것 같았다.

이론을 본 후 다시 작성했다.

 

2부터 시작하여 n까지 배열이 있는데 2면 2의 배수를 전부 다 색칠하고, 3이면 3의 배수 색칠.. n이면 n의 배수를 전부 색칠하면서 처음부터 소수를 찾아 answer 리스트에 추가하는 식으로 진행하였다.

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

ch = [0] * 1000001
answer = []

for i in range(2, n+1):
    if ch[i] == 0:
    
        if m<=i<=n:
            answer.append(i)
            
        for j in range(i, n+1, i):
            ch[j] += 1

for i in answer:
    print(i)

 

완성