백준 17103 문제 풀이 python
🐒 골드바흐 파티션
https://www.acmicpc.net/problem/17103
✍ 나의 풀이
import sys
t = int(input())
arr = [True for _ in range(1000001)]
for i in range(2,1001):
if arr[i]:
for j in range(i + i , 1000001, i):
arr[j] = False
for _ in range(t):
result = 0
n = int(sys.stdin.readline().rstrip())
for i in range(2,n//2+1):
if arr[i] and arr[n-i]:
result += 1
print(result)
제출할때마다 왜 시간초과가 나오나 했는데 지금까지 에라토스테네스의 체를 반복문 안에서 계속 만들고 있었다..
🧠 문제 이해
골드바흐의 추측 응용문제이다.
2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.
- 에라토스테네스의 체를 이용해 주어진 정수까지의 소수를 찾아내고
- 주어진 정수를 소수들의 합으로 나타낼 수 있는 가짓수를 출력해야한다.
에라토스테네스의 체는 한번 만들어놓고 여러번 사용할 수 있을때 쓰는게 시간적으로 효율적인 것 같다.
Author And Source
이 문제에 관하여(백준 17103 문제 풀이 python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mauserne/백준-17103-문제-풀이-python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)