[백준] 1929번 소수 구하기 파이썬 풀이 코딩테스트 연습 기본 수학2 실버2

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

1929번: 소수 구하기

 

문제

 

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

 

입력

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

 

출력

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

 

예제 입력 1

3 16

 

예제 출력 1

3
5
7
11
13

 

이번 문제는 소수를 구할 때 시간초과가 안뜨게 조절해야하는 문제였습니다

num, target = map(int,input().split())

arr = []
tmp = 1
if num %2 == 0:
    num-=1
print(2)

for i in range(num, target+1, 2):
    bool = True
    
    if i == 3 or i == 5 or i ==7 or i == 11:
        print(i)
        arr.append(i)
        continue
    elif i%3 == 0 or i%5 == 0 or i%7 == 0 or i%11 == 0:
        continue
    elif i == 1 :
        continue
    
    for j in arr:
        if i % j == 0:
            bool = False
            break
    if bool:
        print(i)
        arr.append(i)

처음에는 문제를 이렇게 하였지만 다시생각해보니 2를 하는게 아니라 1/2을 곱해주어서 더 효율적으로 소수인지 아닌지 값을 확인하는 것을 생각해냈습니다.

 

x, y = map(int, input().split())

for i in range(x, y+1):
    if i == 1:
        continue
    for j in range(2, int(i** 0.5)+1 ):
        if i%j==0:
            break
    else:
        print(i)

확실히 두번째 작성한 코드가 더 간결하네요 ** 0.5로 반까지만 확인을 시켜주면 됩니다!

 

옛날에 비슷한 문제를 풀었던 것이 기억이 났네요 ㅎㅎ