Notice
Recent Posts
Recent Comments
Link
궤도
[백준] 6588번 : 골드바흐의 추측 본문
문제
풀이
홀수인 두 소수의 합으로 짝수를 나타내는 문제이다.
홀수인 두 소수이므로 3부터 시작하면 될 것이고 입력값의 절반까지만 탐색하면 된다.
만약 입력이 8이라면 3+5와 5+3은 같은 말이기 때문이다.
그리고 두 소수의 차가 가장 큰 것을 출력하라고 했는데 그럼 뭐 3부터 탐색하다가 두 소수를 찾으면 바로 출력하면된다.
20은 3+17로도 나타낼 수 있고 7+13으로도 나타낼 수 있지만 두 수의 차가 가장 큰 것은 먼저 발견된 3+17이다.
이 소수를 찾는 과정에서 시간초과가 나지 않도록 빠르게 구하는 것이 중요하다.
나는 에라토스테네스의 체를 사용했다.
[백준] 1929번 : 소수 구하기
문제 풀이 에라토스테네스의 체를 이용해 소수를 구하는 문제다. 에라토스테네스의 체가 무엇이냐고 물어본다면... 이런식으로 특정 소수의 배수를 전부 지우는 과정을 통해 소수를 구하는 방
myunji.tistory.com
여기에서 구현했었다.
처음엔 input이 들어올 때마다 에라토스테네스의 체를 실행했는데 시간초과가 발생했다.
생각해보니 max input이 1000000이므로 처음에 그냥 그 범위의 수에 대한 에라토스테네스의 체를 실행하면 되는 일이었다.
소스코드
#include <iostream>
#include <cmath>
using namespace std;
const int MAX = 1000000;
bool isPrime[MAX];
void eratos() { //에라토스테네스의 체
fill(isPrime+2, isPrime+MAX, 1); //0과 1은 소수가 아님
int line = sqrt(MAX) + 1; //제곱근까지만 계산
for (int i = 2; i <= line; i++) {
if (isPrime[i]) { //소수의 배수들을 모두 false 처리
for (int j = i * 2; j < MAX; j += i)
isPrime[j] = false;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int input;
eratos(); //미리 소수 전부 찾아 놓음
while (true) {
bool isGoldbach = false;
cin >> input;
if (input == 0) //종료조건
break;
for (int i = 3; i <= (input / 2); i++) { //3부터 input의 절반까지 소수 탐색
if (isPrime[i] && isPrime[input - i]) {
isGoldbach = true;
cout << input << " = " << i << " + " << input - i << '\n';
break;
}
}
if (!isGoldbach) //소수의 합으로 나타낼 수 없음
cout << "Goldbach's conjecture is wrong.\n";
}
}
전체 소스코드다.
const int MAX = 1000000;
bool isPrime[MAX];
void eratos() { //에라토스테네스의 체
fill(isPrime+2, isPrime+MAX, 1); //0과 1은 소수가 아님
int line = sqrt(MAX) + 1; //제곱근까지만 계산
for (int i = 2; i <= line; i++) {
if (isPrime[i]) { //소수의 배수들을 모두 false 처리
for (int j = i * 2; j < MAX; j += i)
isPrime[j] = false;
}
}
}
input을 받기 전 1000000보다 작은 모든 소수를 찾아낸다.
eratos(); //미리 소수 전부 찾아 놓음
while (true) {
bool isGoldbach = false;
cin >> input;
if (input == 0) //종료조건
break;
for (int i = 3; i <= (input / 2); i++) { //3부터 input의 절반까지 소수 탐색
if (isPrime[i] && isPrime[input - i]) {
isGoldbach = true;
cout << input << " = " << i << " + " << input - i << '\n';
break;
}
}
if (!isGoldbach) //소수의 합으로 나타낼 수 없음
cout << "Goldbach's conjecture is wrong.\n";
}
3부터 시작해서 a, b 둘 다 소수인 경우를 찾으면 바로 출력하고 break 한다.
Comments