1. 골드바흐의 추측1) 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.2) 위의 문장에 3을 더하면3) 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다.4) 아직 증명되지 않은 문제 => 추측5) 10^18 이하에서는 참인 것이 증명됨 -6588번(골드바흐의 추측)=>10^6 이하의 짝수에 대해서 골드 바흐의 추측을 검증하는 문제#include using namespace std; int pn;int p[1000000];bool c[1000001];int main(void) {int n; // 2부터 100만 사이의 소수 구하기for (int i = 2; i n;if (n == 0)break;for (int i = 1; i < pn; i++) {if (c[n - p[i]] == fals..
1. 어떤 수 N이 소수인지 아닌지 알아내는데 걸리는 시각 복잡도가 O(루트N) 이라고 하면,1부터 N까지 범위에서 모든 소수를 구하는데 걸리는 시간 복잡도는 O(N루트N) 만큼의 시간이 걸린다.N이 백만인 경우, 1,000,000 * 1,000 = 10^9 = 10억 = 10초 가 걸린다.너무 긴 시간이 필요하므로 이 경우에는 에라토스테네스의 체를 사용한다. 2. 에라토스테네스의 체-1부터 N까지 범위 안에 들어가는 모든 소수를 구할 때 사용1)2부터 N까지 모든 수를 써놓는다.2)아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.3)그 수는 소수이다.4)이제 그 수의 배수를 모두 지운다. (코드)N이 100 이라고 하면, int p[100]; // 소수 저장int pn=0; // 소수의 개수boo..