백준 알고리즘 1929번(파이썬)

 

백준 1929번_파이썬 알고리즘

Q. 백준 1929. 소수 구하기

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오
(1) 입력 : 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

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

 

입력 예시	출력 예시
3 16	3 5 7 11 13

 

---

A. 풀이

# Q 백준 1929. 소수 구하기 (시간초과)
M, N = [int(x) for x in input().split(' ')] 
num_list = [x for x in range(M, N+1)]
new_list = []
test = 0

for x in num_list:
    test = 0
    if x == 1:
        continue
    elif x == 2:
        new_list.append(2)
    else:
        for i in range(2, x):
            if x % i == 0:
                test += 1
                break
        if test == 0:
            new_list.append(x)
            
for i in new_list:
    print(i)

# Q 백준 1929 소수 구하기 (함수지정, 동일하게 시간초과)
def is_prime_num(n):
    for i in range(2, n):
        if n % i == 0:
            return False # i로 나누어 떨어지면 소수가 아니므로 False 리턴
    
    return True # False가 리턴되지 않고 for문을 빠져나왔다면 소수이므로 True 리턴

M, N = [int(x) for x in input().split(' ')] 
num_list = [x for x in range(M, N+1)]
new_list = []
test = 0

for x in num_list:
    if x == 1:
        continue
    elif is_prime_num(x):
        new_list.append(x)

print(new_list)

1) 약수의 특성 

 - 특정 수 N의 약수들을 일렬로 나열했을 때 그 중 가운데의 수를 중심으로 약수가 대칭인 성격

2) 에라토스테네스의 체 알고리즘
 - 2~N까지의 리스트를 만들고 해당 배열의 가장 작은 수 i부터 시작하여 i의 배수들을 해당 배열에서 지워준다.
 - 주어진 범위 내 i의 배수가 모두 지워지면 i다음으로 작은수의 배수를 동일하게 지워준다.
 - 더 이상 반복할 수 없을 때까지 반복 한다

 

# ※ 참고. 에라토스테네스의 체를 활용한 문제풀이
import math

def is_prime_num(n):
    arr = [True] * (n + 1) # 특정 수가 지워졌는지 아닌지 확인하기 위한 배열
    arr[0] = False
    arr[1] = False

    for i in range(2, int(math.sqrt(n) + 1)):
        if arr[i] == True: # 특정 수가 지워지지 않았다면 (소수여서)
            j = 2

            while (i * j) <= n:
                arr[i*j] = False # i의 배수의 값을 False로 지워준다.
                j += 1

    return arr

M, N = [int(x) for x in input().split(' ')] 
new_list = []

arr = is_prime_num(N) # 0 ~ 50중 소수를 구하기 위한 함수

for i in range(len(arr)):
    if arr[i] == True:
        new_list.append(i)
        
print(new_list)

에라토스테네스의 체를 활용한 풀이법

# Q 백준 1929 소수 구하기 ★★★☆
import math

m, n = [int(x) for x in input().split(' ')] 
arr = [True for _ in range(n+1)]

for i in range(2, int(math.sqrt(n)) + 1):
    if arr[i] == True:
        j = 2
        while i * j <= n:
            arr[i*j] = False
            j += 1

for i in range(m, n+1):
    if i > 1:
        if arr[i] == True:
            print(i)