글 읽기 - 테스트케이스 추가 필요

hoan123432 2년 전 2

다른 사람들은 어떤 아이디어로 했는지 보면서, 발견한 문제점입니다.

현재 테스트 케이스는 n = a + b에서 a,b가 짝수일때도 통과시키는 문제점이 있습니다.

(아래코드에서 "a = n - i, b = i"일 때, i를 1씩 감소시키게 되면 a,b는 짝수일 확률이 존재하기 때문입니다.)

만약 이 코드를 고친다면 "짝수 - 홀수 = 홀수"라는 수의 규칙을 활용해 "기존 for문(line 21)"을 "for (int i = n - 1;i >= (int)sqrt(n);i -= 2)"으로 수정해야합니다.

즉, i = n -1인 '홀수값'으로 시작해서 2씩 빼주어서 a,b가 항상 홀수임을 보장해주어야합니다.

#include <iostream>
#define MAX 1000001

using namespace std;

int a[MAX];

int main(void) {
	a[1] = 1;
	for(int i = 2; i <= MAX; i++) {
		for(int j = i * 2; j <= MAX; j += i) {
			if(a[j] == 1) continue;
			else a[j] = 1;
		}
	}
	while(1) {
		int n;
		scanf("%d", &n);
		if(n == 0) break;
		bool find = false;
		for(int i = n; i >= n / 2; i--) {
			if(a[i] == 0 && a[n - i] == 0) {
				printf("%d = %d + %d\n", n, n - i, i);
				find = true;
				break;
			}
		}
		if(!find) {
			printf("Goldbach's conjecture is wrong.\n");
		}
	}
	return 0;
}

g072923 2년 전 1

짝수인 소수는 2밖에 없어서 상관없을 듯 합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

테스트케이스 추가 필요

hoan123432 2년 전 2

g072923 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말