6588번: 골드바흐의 추측
각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰
www.acmicpc.net
코드
#include <stdio.h>
#include <stdbool.h>
const int MAX = 1000001;
int is_prime[1000001];
void prime(int n){
is_prime[0] = 1;
is_prime[1] = 1;
for(int i=2;i<MAX;i++){
if(is_prime[i]==0){
for(int j=i*2;j<MAX;j+=i){
is_prime[j]= 1;
}
}
}
}
int main() {
prime(MAX);
while(1){
int n;
bool flag = false;
scanf("%d",&n);
if(n==0) break;
for(int i=3;i<=n/2;i+=2){
int j = n-i;
if(j%2==1 && is_prime[i]==0&&is_prime[j]==0){
printf("%d = %d + %d\n", n, i, j);
flag = true;
break;
}
}
if(!flag){
printf("Goldbach's conjecture is wrong.\n");
}
}
return 0;
}
계속 25퍼센트에서 틀리길래 반례를 찾아서 해결했다
6
0
이걸 입력하면
6 = 3 + 3
이렇게 나와야 하는데 27번째 줄에서 for문의 종료 조건식을 i<n/2로 해놔서 계속 틀렸었다...같은 홀수 소수끼리 더해서 짝수를 만들 수 있다는 걸 간과했다
'문제풀이 > C, C++' 카테고리의 다른 글
[C++] 백준 10867번 중복 빼고 정렬하기 (0) | 2024.05.17 |
---|---|
[C언어] 백준 14916번 거스름돈 (0) | 2023.11.20 |
[C언어] 백준 10828번 스택 (0) | 2023.11.17 |
[C언어] 백준 1094번 막대기 (0) | 2023.11.16 |
[C언어] 백준 2302번 극장 좌석 (0) | 2023.11.16 |