728x90
반응형
- 문제
- 잘못된 풀이
import sys
while True:
n = int(sys.stdin.readline())
if n == 0: # 0이면 끝
break
prime_list = []
for i in range(n, 2*n): # n~2n까지의 수에서
check = 0
for j in range(2, int(i**0.5)+1): # 2 ~ 루트n
if i%j == 0: # 나누어 떨어지면 소수 아님
check = 1
break
if check == 0:
prime_list.append(i)
print(prime_list)
print(len(prime_list))
해당 문제도 주어지는 범위 내에서 소수를 구하는 문제이다.
이전 포스팅에서 소수를 다루었듯이 해당 문제도 동일한 로직으로 해결하면 된다고 생각했는데 '시간초과'로 해결하지 못했다.
- 올바른 풀이
import sys
def check_prime(N):
prime_ = [True] * (N) # list를 먼저 만들어주고
for i in range(2, int(N**0.5)+1): # 2부터 제곱근 n까지
if prime_[i]: # true이면
for j in range(i*2, N, i): # 각 배수들을 false로 만듦
prime_[j] = False
return [i for i in range(2, N) if prime_[i] == True]
while True:
n = int(sys.stdin.readline())
if n == 0:
break
prime_list = check_prime(2*n+1) # n부터 2n 사이의 있는 소수
answer_list = [num for num in prime_list if num > n] # n보다 큰 수 뽑기
print(len(answer_list))
이번에는 문제를 함수로 나누어 풀어보았다.
에라토스테네스의 체 풀이방법으로 해결했다.
prime_이라는 list를 먼저 만들어주고, 2부터 제곱근 n까지 각 배수들을 false로 만들어 소수만 prime_list에 저장한다.
prime_list 안에 있는 소수들은 2부터 2n보다 작은 수들로 이루어져있기 때문에,
answer_list에서 n보다 큰 (2n보다 작은) 소수들만 남기는 형태로 문제를 해결한다.
728x90
'자료구조 및 알고리즘 > 백준' 카테고리의 다른 글
[python] 11728. 배열 합치기 (0) | 2023.01.16 |
---|---|
[python] 9020. 골드바흐의 추측 (0) | 2023.01.14 |
[python] 1929. 소수 구하기 (0) | 2023.01.12 |
[python] 2581. 소수 (0) | 2023.01.12 |
[python] 1978. 소수 찾기 (2) | 2023.01.12 |