백준 6588번 골드바흐의 추측 C++

이 문제는 제한 시간이 0.5s 이므로 O(Nlog(logN))으로 풀어야 한다. 따라서 에라토네스의 체를 사용해야한다.

문제를 풀면서 의문이 들었다. 바로 rst 함수 안의 for문에 i를 i--로 하면 시간 초과가 나고, i를 i++로 하면 시간 초과가 말생하지 않는다는 것이다. 

이 문제는 아직 이유를 모르겠다.

#include <iostream>

using namespace std;

int prime[1000000];
int pn = 0;
bool check[1000001] = { false };

int p() {
	check[0] = check[1] = true;
	for (int i = 2; i <= 1000000; i++) {
		if (check[i] == false) {
			prime[pn++] = i;
			for (int j = i + i; j <= 1000000; j += i) {
				check[j] = true;
			}
		}
	}
	return 0;
}

int rst(int n) {
	for (int i = 0; i <= pn; i++) {
		if (prime[i] > 1) {
			if (check[n - prime[i]] == false) {
				cout << n << " = " << prime[i] << " + " << n - prime[i] << '\n';
				return 0;
			}
		}
	}
	return -1;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	p();

	while (1) {
		int n;
		cin >> n;
		if (n == 0) {
			break;
		}
		else {
			if (rst(n) == -1)
				cout << "Goldbach's conjecture is wrong.\n";
		}
	}

	return 0;
}

 

#include <iostream>

using namespace std;

int prime[1000000];
int pn = 0;
bool check[1000001] = { false };

int p() {
   check[0] = check[1] = true;
   for (register int i = 2; i <= 1000000; i++) {
      if (check[i] == false) {
         prime[pn++] = i;
         for (register int j = i + i; j <= 1000000; j += i) {
            check[j] = true;
         }
      }
   }
   return 0;
}

int rst(int n, int i) {
   for (i; i >= 0; i--) {
      if (n - prime[i] > 2) {
         if (check[n - prime[i]] == false) {
            cout << n << " = " << n - prime[i] << " + " << prime[i] << '\n';
            return 0;
         }
      }
   }
   return -1;
}

int main(void) {
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);

   p();

   while (1) {
      int n;
      cin >> n;
      if (n == 0) {
         break;
      }
      else {
         if (rst(n, pn) == -1)
            cout << "Goldbach's conjecture is wrong.\n";
      }
   }

   return 0;
}