c언어 6588번 골드바흐의 추측 (백준)

#include <stdio.h>

int main(void) {
	char sosu[1000002] = {1, 1}; //소수는 0, 아닌건 1로 저장
	int arr[80001] = {}; //소수들을 오름차순으로 저장하는 배열
	
	int p = 0; //소수들을 저장하는 데 사용하는 변수
	for(long long i=2; i<=1000000; i++) { //2부터 소수와, 아닌 것 구별하기
		while(sosu[i]) i++; //소수가 아니라면 반복
		if(i>1000000) break; //1000000까지 다 했다면 종료
		
		for(long long j = i*i; j<=1000000; j+=i) sosu[j] = 1; //소수의 배수는 소수가 아님을 이용합니다.
		
		arr[p++] = i; //소수 저장
	}
	
	while(1) { //두 홀수 소수의 합으로 나타낼 수 있는지 판단하기
		int tmp;
		scanf("%d", &tmp);
		if(!tmp) break; //0 입력시 종료
		
		for(int i=1; ; i++) { //arr[0] = 2이다. 문제에선 홀수인 소수를 이용하기 때문에, arr[1]부터 사용해야한다 고로 i의 초기값은 1이다.
			int tmp2 = tmp-arr[i]; //입력받은수 - 소수
			
			if(arr[i] > tmp2) { //만약 소수가 입력받은수 - 소수보다 크다면, 이는 반복을 할 의미가 없다. 홀수인 소수 두개로 만들수 없음을 의미한다.
				printf("Goldbach's conjecture is wrong.\n");
				break; //종료
			}
			
			if(!sosu[tmp2]) { //만약 입력받은수 - 소수 도 소수라면, 이는 두 홀수인 소수의 합으로 나타낼 수 있음을 의미한다.
				printf("%d = %d + %d\n", tmp, arr[i], tmp2);
				break; //종료
			}
		}
	}
}

풀이 : 소수 판별

 

1. 1~1000000 에서 소수이면 0, 아니라면 1로 저장하는 배열을 준비 한다음
반복문을 이용하여 소수가 아닌 것은 1로, 소수인 것은 따로 배열을 만들어서 차곡차곡 저장해줍니다.
(2, 3, 5, 7 ...)

2. 골드바흐의 추측에선 홀수 인 소수를 사용하기 때문에 3부터 시작합니다.

3. 어떤 수를 입력받으면 반복문을 이용하여, 소수만 따로 저장한 배열을 이용하여
만약 어떤수 - 소수 가 소수라면 이를 출력하면 되며
만약 반복중에 어떤수 - 소수가 소수보다 작아지게 되면, 이는 두 홀수 인 소수로는 만들 수 없는 수라는 의미가 되며 반복을 종료하고
문제에서 말하는 구문을 출력합니다.

4. 0이 입력되면 반복문을 종료합니다.

 

https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측