#include <iostream> using namespace std; int main() { int i, j, m, n, a[1000001] = { 0,1 }; cin >> m >> n; for (i = 2; i <= n; i++) { for (j = 2; i*j <= n; j++) a[i*j] = 1; } for (i = m; i <= n; i++) if (!a[i]) cout << i << endl; return 0; } |
시간초과가 나오는데, 어떻게 풀어야 하는지 ? 시간 초과가 나옵니다. |
#include<iostream> using namespace std; const int MAX = 1000000; bool c[MAX + 1]; int main() { c[0] = c[1] = true; for (int i = 2; i*i <= MAX; i++) { if (c[i] == false) { for (int j = i*i; j <= MAX; j = j + i) c[j] = true; } } int m, n; cin >> m >> n; for (int i = m; i <= n; i++) { if (c[i] == false) cout << i << '\n'; } return 0; } |
공식처럼 있는 것이므로 이것도 기억하고 있어야합니다. |