글 읽기 - 골드 바흐의 추측 반례부탁드립니다.. 50퍼에서 틀리네요..

shj1504 4년 전 0

반례부탁드립니다 ㅜㅜ

도저히 못찾겠습니다.ㅡㅡ

#include <iostream>
#include <cmath>
using namespace std;
int n, arr[1000001];
int prime[1000001], idx, flag;

void getprime() {
	//cout << sqrt(n) << "\n";
	for (int i = 2; i <= (int)sqrt(1000001); i++) {
		if (arr[i])continue;
		for (int j = i + i; j < 1000001; j += i) {
			if (arr[j])continue;
			if (arr[j] == 0) {
				//cout << j;
				arr[j] = 1;
			}
		}
	}

	for (int i = 3; i < 1000001; i++) {
		if (arr[i] == 0) {
			prime[idx++] = i;
		}
	}



}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;

	getprime();
	//for (int i = 0; i < idx; i++) {
	//	cout << prime[i] << " ";
	//}

	while (n != 0) {

		flag = 0;
		int j = 0;

		for (int i = 0; i < idx; i++) {
			//cout << i << " "<<j <<"\n";
			for (; j < idx; j++) {
				if (prime[i] + prime[j] == n) {

					cout << n << " = " << prime[i] << " + " << prime[j] << "\n";
					flag = 1;
					break;
				}
				else if (prime[i] + prime[j] > n) {
					//cout << j << " " <<"\n" ;
					j--; break;
				}
				
			}
			if (idx == j)j--;
			if (flag)break;

		}
		if (!flag)cout << "Goldbach's conjecture is wrong.\n";
		cin >> n;
	}


	return 0;
}

eggfries 4년 전 0

이 글을 보니 컴퓨터로 여러 수학 난제를 푸는 것이 굉장히 흥미롭게 느껴지네요^^ 저는 C++으로 코드를 안 짜서 답변은 못 드릴 것 같네요

jh0956 4년 전 0

코드를 끝까지 읽어보진 않았지만

getprime 함수 20줄에 반복문이 3부터 시작하게 하셨는데

!arr[i] 가 소수라면 2부터 시작해야하지 않을까요

shj1504 4년 전 0

jh0956 문제조건이 그렇습니다.

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

문제

문제

출처

ICPC

골드 바흐의 추측 반례부탁드립니다.. 50퍼에서 틀리네요..

shj1504 4년 전 0

eggfries 4년 전 0

jh0956 4년 전 0

shj1504 4년 전 0

jh0956 문제조건이 그렇습니다.

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말