백준 1929

<소수 구하기> 문제

난이도: 실버 4
1. 백준 문제
링크텍스트

2. 코드 알고리즘
   

3. 코드

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

import sys
import math
input = sys.stdin.readline

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

a= [0]*(n+1)

for i in range(2, n+1):
    a[i] = i

for i in range(2, int(math.sqrt(n))+1):#2부터 시작
    #2부터 시작하면 3...16
    for j in range(i+i,n+1,i): #if문을 따로 설정하는 것이 아닌 for문 내에서 해결가능하므로
        #i+i ... i의 배수만 고려하기! i는 고려 제외
        a[j] = 0 #i의 배수는 모두 0으로! 4 234
#j=2 i
#    for j in range(n-m+1): #if문을 따로 설정하는 것이 아닌 for문 내에서 해결가능하므로
#        if(a[j]==i or a[j]==0):
#            continue
#        elif (a[j]%i==0): #계속 길이가 줄어듬
#            a[j] = 0

#합성수 다 제거
for i in range(m, n+1):
    if a[i] !=0:
        print(a[i])

4. 후기

음.. 비슷하게는... 큰 알고리즘은 틀리지 않았음.
단, 나의 코드는 중복이 있어서
시간초과가 뜸
그 중복을 제거하기 위해 혼자서 생각해내기 어려운 부분들이 있었음.

sqrt(n)까지만 진행해야 한다는 점
if, elif문을 사용하지 않고 for문 내에서 i만큼 간격씩 띄우며 진행해 중복을 제거할 수 있었다는 점

중복을 알아차리는 것도
고치는 것도 어려운것 같다...