문제
리뷰
두 홀수 소수의 합으로 N을 나타낼 수 있는지 검사하는 문제다.
짝수 정수 N의 범위 (6 ≤ N ≤ 1000000)
에라토스테네스의 체 문제 소수 구하기 백준 1929번를 풀어보고 나니까 막막하진 않았다.
문제의 풀이과정은 아래와 같다.
- 에라토스테네스의 체로 백만 까지의 소수를 모두 구한다. (Eratos 함수 )
- Prime 벡터에 홀수 소수들만 저장한다. (Eratos 함수 )
- Prime 벡터를 순회하면서 N-Prime[i] 가 Prime 에 있는지 검사한다. ( Gold 함수 )
Gold 함수 case1
2중 for문으로 작성한 형태
bool Gold(int n){ // Prime 을 순회하면서 n을 a+b로 나타낼수 있는지 확인
for(int i = 0; Prime[i] < n; i++){ // a와 b는 n보다는 작을테니 n 직전까지만 탐색
int target = n - Prime[i]; // n = a + b 가 되어야 하니까 b를 찾아본다.
for(int j = i; Prime[j] < n; j++){
if(target == Prime[j]){
printf("%d = %d + %d\n", n, Prime[i], Prime[j]);
return true;
}
}
}
return false;
}Gold 함수 case2
for문을 1개로 쓴 형태
bool Gold(int n){
for(int i = 0; Prime[i] < n; i++){ // a와 b는 n보다는 작을테니 n 직전까지만 탐색
if(n-Prime[i] == A[n-Prime[i]]){ // n-Prime[i] 값이 소수인지 확인한다
printf("%d = %d + %d\n", n, Prime[i], n-Prime[i]);
return true;
}
}
return false;
}Gold 함수의 내부 for문에서 j를 i+1로 초기화 하고 시작했다가 틀렸다.
입력으로 6을 넣었을 때, 6 = 3 + 3 으로 표현할 수 있다. 따라서 내부 for문은 j = i로 초기화 해야 한다.
맞은 코드1
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 1000001
using namespace std;
int A[1000001]; // 모든 소수
vector<int> Prime; // 홀수 소수
void Eratos(void){ // 백만 까지의 소수를 모두 구한다.
A[0] = A[1] = 1; // 0과 1은 소수가 아니다.
for(int i = 2; i<= MAX; i++){
A[i] = i; // A배열 값을 '자기 자신'으로 저장한다.
}
for(int i = 2; i*i <= MAX; i++){
if(A[i] == i){
for(int j = i*i; j <= MAX; j+=i){
A[j] = i; // 소수의 배수들을 지운다
}
}
}
// 홀수인 소수만 Prime에 저장
for(int i = 3; i<= MAX; i++){
if(A[i] == i) Prime.push_back(A[i]);
}
}
bool Gold(int n){ // Prime 을 순회하면서 n을 a+b로 나타낼수 있는지 확인
for(int i = 0; Prime[i] < n; i++){
int target = n - Prime[i];
for(int j = i; Prime[j] < n; j++){
if(target == Prime[j]){
printf("%d = %d + %d\n", n, Prime[i], Prime[j]);
return true;
}
}
}
return false;
}
int main(void){
Eratos();
while(1){
int n = 0;
scanf("%d", &n);
if(n == 0) break;
if(!Gold(n)) cout << "Goldbach's conjecture is wrong.\n"<<'\n';
}
return 0;
} 맞은 코드2
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 1000001
using namespace std;
int A[1000001]; // 모든 소수
vector<int> Prime; // 홀수 소수
void Eratos(void){
A[0] = A[1] = 1; // 0과 1은 소수가 아니다
for(int i = 2; i<= MAX; i++){
A[i] = i; // 자기 자신을 저장시킨다
}
for(int i = 2; i*i <= MAX; i++){
if(A[i] == i){
for(int j = i*i; j <= MAX; j+=i){ // 소수의 배수들을 지운다
A[j] = i;
}
}
}
for(int i = 3; i<= MAX; i++){ // 홀수인 소수만 Prime에 저장
if(A[i] == i) Prime.push_back(A[i]);
}
}
bool Gold(int n){
// P 를 순회하면서 n을 a+b로 나타낼수 있는지 확인
for(int i = 0; Prime[i] < n; i++){
if(n-Prime[i] == A[n-Prime[i]]){
printf("%d = %d + %d\n", n, Prime[i], n-Prime[i]);
return true;
}
}
return false;
}
int main(void){
Eratos();
while(1){
int n = 0;
scanf("%d", &n);
if(n == 0) break;
if(!Gold(n)) cout << "Goldbach's conjecture is wrong.\n"<<'\n';
}
return 0;
} 728x90
'알고리즘 > 백준' 카테고리의 다른 글
| 조합 0의 개수 백준 2004번 (0) | 2020.09.15 |
|---|---|
| 소인수분해 백준 11653번 (0) | 2020.09.14 |
| 소수 구하기 백준 1929번 에라토스테네스의 체 (0) | 2020.09.14 |
| 소수 찾기 백준 1978번 (0) | 2020.09.13 |
| 팩토리얼 0의 개수 백준 1676번 c++ (0) | 2020.09.12 |