문제
[ 문제 조건 ]
- 골드바흐 수 : 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다.
- 골드바흐 파티션이 여러개 인 경우는 두 소수의 차가 가장 작은 것이 답
[ 해결순서 ]
이 문제를 해결하기 전에 에라토스테네스의 체가 무엇인지 알아야한다.
소수인 값을 하나씩 기준으로 (이 값을 N이라 치자) N의 배수를 범위 내에 모두 지운다. 이걸 반복하고 반복문을 빠져나왔을 때 지워지지 않은 값이 소수인 것이다.
에라토스테네스의 체 코드
n = 100 a = [False,False] + [True]*(n-1) primes = [] for i in range(2, n+1): #n까지임 if a[i]: #값이 들어있으면 primes.append(i) # 2*i 인 이유는 그 값 이후의 두배 값부터 시작해야되므로 for j in range(2*i, n+1, i): #2*i~n+1까지 i만큼 a[j] = False print(primes)
먼저 에라토스테네스의 체 알고리즘으로 소수를 구했다.
이 때 prime 배열에는 소수인 값은 True가 되어있다.
이제 입력받은 각 값을 비교하는데 절반을 나누어서 반복 비교한다 ( 절반으로 나눠야 두개를 합쳤을 때의 값이 입력 값이 나오기 때문에 )
값을 하나는 늘리고, 하나는 줄여서 두개의 값 모두 소수일 때 값을 출력하고 반복문을 빠져나온다.
✏️한줄평
: 에라토스테네스의 체(이름 한번 치기 넘 길다)에 대한 개념과 코드를 상기시킬 수 있는 문제였고, 그에 조금 더 응용된 문제였다.
코드
'알고리즘' 카테고리의 다른 글
[Python] 백준 2468번 - 안전 영역 (0) | 2021.08.09 |
---|---|
[Python] map 함수로 2차원배열의 최대값 구하기 (0) | 2021.08.09 |
[Python] 백준 11052번 - 카드 구매하기 (0) | 2021.08.06 |
[JAVA] 백준 1245 - 농장 관리 (0) | 2021.07.26 |
[JAVA] 백준 11057 - 오르막 수 (0) | 2021.07.25 |