#include <stdio.h> #include <iostream> #define SIZE 10001 using namespace std; int isNotPrime[SIZE]; void eratosthenes() { for (int i = 2; i*i < SIZE; i++) if (!isNotPrime[i]) for (int j = i*i; j < SIZE; j += i) isNotPrime[j] = 1; isNotPrime[1] = 1; } void goldBach(int n) { int i, j, mid = n >> 1; for(i=j=mid; i<=n; i--, j++) if (!isNotPrime[i] && !isNotPrime[j]) { cout << i << " " << j << endl; return; } } void main() { eratosthenes(); int n, t; cin >> t; while (t--) { cin >> n; goldBach(n); } } |
오케이, 에라토스테네스를 함수르 만들었습니다. 이것을 보면 아이를 2부터 시작하고 아이제곱보다 작으래까지 돌리고 그 안에 이프문을 넣어서 먼저 숫자이가 들어가면 0이기때문에 2가 들어가고 2가 아니라 제곱수인 4부터 시작해서 4 6 8 을 다 1로 만들어 나갑니다. 그리고 다음 포문에서는 3부터 시작하고 들어갑니다. 오케이 제이 제곱하는 것이랑 제이는 사이즈보다 작음은 이해가 가는데, 왜 처음 포문에서 아이 제곱은 사이즈보다 작다 이렇게 나오는 것이지? 10000 이면 100 이후에는 소수가 존재하지 않는 것인가? 아까 중복으로 시작하는 이유가 무엇이라고 했지 10, 중복이 없을때 부터 배수를 지우려면 제곱한 수부터 배수를 지우면 됩니다. |