https://www.acmicpc.net/problem/4948
๋ฒ ๋ฅดํธ๋ ๊ณต์ค์ ์์์ ์์ฐ์ n(1 โค n โค 123,456)์ ๋ํ์ฌ, n๋ณด๋ค ํฌ๊ณ , 2n๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์๋ ์ ์ด๋ ํ๋ ์กด์ฌํ๋ค๋ ๋ด์ฉ์ ๋ด๊ณ ์๋ค.
์๋ฅผ ๋ค์ด, 10๋ณด๋ค ํฌ๊ณ , 20๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์๋ 4๊ฐ๊ฐ ์๋ค. (11, 13, 17, 19) ๋, 14๋ณด๋ค ํฌ๊ณ , 28๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์๋ 3๊ฐ๊ฐ ์๋ค. (17,19, 23)
์์ฐ์ n์ด ์ฃผ์ด์ก์ ๋, n๋ณด๋ค ํฌ๊ณ , 2n๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ์ ์ฌ๋ฌ ๊ฐ์ ํ ์คํธ ์ผ์ด์ค๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ๊ฐ ์ผ์ด์ค๋ n์ ํฌํจํ๋ ํ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๋ค.
์ ๋ ฅ์ ๋ง์ง๋ง์๋ 0์ด ์ฃผ์ด์ง๋ค.
๊ฐ ํ ์คํธ ์ผ์ด์ค์ ๋ํด์, n๋ณด๋ค ํฌ๊ณ , 2n๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
์ด ๋ฌธ์ ๋ n์ ๋ฒ์๋ฅผ ์ ๋ด์ผํ๋ ๋ฌธ์ ์ด๋ค. ํ์์ ๋ฐฑ์ค ํ ๋ ์๊ฐ ์์ด ํ๋ฉด n์ ๋ฒ์๋ฅผ ๋ณด๊ณ ๋ฐฐ์ด์ ๊ทธ๋ฅ n์ ๊ฐ์ผ๋ก ๋ฃ์ด๋ฒ๋ฆด ์ ์๋ค.
๋๋ ์ฒ์์ arr[123456]์ ์ ์ธํ๊ณ ๋ฌธ์ ํ์ด๋ฅผ ์ ์ถํ๋๋ฐ ๊ณ์ '๋ฐํ์ ์๋ฌ(Out OF Bound)'๊ฐ ๋์๋ค. ์ด ๋ฐํ์์๋ฌ๋ ๋ณดํต ๋ฐฐ์ด์ ํฌ๊ธฐ๋ฅผ ์๋ชป ์ค์ ํ์ ๋ ๋์ค๋ ์๋ฌ์ธ๋ฐ ๊ทธ ์๋ฌ๋ฅผ ๋ณด๊ณ ๋์์ผ ๋ด๊ฐ ๋ฐฐ์ด ํฌ๊ธฐ ์ค์ ์ ์๋ชปํ๋ค๋ ๊ฒ์ ์์๋คใ
ใ
(2n๊น์ง ๋ด์ผํ๊ธฐ ๋๋ฌธ)
๊ทธ๋ฆฌ๊ณ ์ด ๋ฌธ์ ๋ ์๋ผํ ์คํ ๋ค์ค์ ์ฒด๋ฅผ ์ฌ์ฉํ ์ค ์๋ค๋ฉด ์ด๋ ต์ง ์๊ฒ ํ ์ ์๋ ๋ฌธ์ ์ด๋ค.
#include <iostream>
using namespace std;
int n;
int arr[246912] = { 0 };
void eratos(int start) {
int cnt = 0;
for (int i = 2; i <= 2 * start; i++) {
arr[i] = i;
}
for (int i = 2; i <= 2*start; i++) {
if (arr[i] == 0) continue;
for (int j = i * 2; j <= 2*start; j += i) {
arr[j] = 0;
}
}
for (int i = start+1; i <= 2 * start; i++) {
if (arr[i] != 0) cnt++;
}
cout << cnt << '\n';
}
int main() {
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
while (1) {
cin >> n;
if (n == 0) break;
else eratos(n);
}
return 0;
}