빠똥빠똥
6588번 골드바흐의 추측(에라토스테네스의 체) 본문
#문제링크 : https://www.acmicpc.net/problem/6588
prime : 소수가 아닌 모든 숫자 true로 체크하는 체크 배열
x : 두개의 소수 중 작은 소수
전략 : 에라토스테네스의 체 알고리즘을 이용하여 먼저 prime배열에 소수가 아닌 인덱스를 전부 true로 채워둔다. 그리고 N값을 입력받아, prime배열에서 작은 인덱스부터 bool값이 false인 인덱스(소수)를 찾는다. 그리고 만약에 해당 인덱스를 i라 했을때, prime[N-i]도 false(소수)이면 해당 값들을 덧셈으로 표현하여 출력한다. 만약에, x값에 변동이 없다면 골드바흐의 추측이 틀린것이므로 해당 문구를 출력한다.
'백준' 카테고리의 다른 글
| 15711번 환상의 짝꿍(골드바흐의 추측, 에라토스테네스의 체) (0) | 2020.05.25 |
|---|---|
| 1644번 소수의 연속합(에라토스테네스의 체, 두 포인터) (0) | 2020.05.22 |
| 2485번 가로수(유클리드 호제법, 최대공약수) (0) | 2020.05.22 |
| 2661번 좋은 수열(DFS, str.substr(), equal(), DFS한번 출력) - ☆ (0) | 2020.05.22 |
| 2580번 스도쿠(DFS) - ☆ (0) | 2020.05.21 |
'백준' Related Articles
more
