์๊ฐ ์ ํ | ๋ฉ๋ชจ๋ฆฌ ์ ํ | ์ ๋ต ๋น์จ |
1 ์ด | 128 MB | 69.799 % |
6359๋ฒ: ๋ง์ทจํ ์๋ฒ
๋ฌธ์ ์๊ฐ๋ํ๊ต ๊ณค์๊ฐ ๊ธฐ์์ฌ์ ์งํ์๋ n๊ฐ์ ๋ฐฉ์ด ์ผ๋ ฌ๋ก ๋์ด์ ๊ฐ์ฅ์ด ์๋ค. ๊ฐ ๋ฐฉ์๋ ๋ฒ์ ์ ๋ง์ด ๋ฐ์ ํ์์ด ๊ตฌ๊ธ๋์ด์๋ค. ๊ทธ๋ฌ๋ ์ด๋ ๋ , ๊ฐ์ฅ ๊ฐ์์ธ ์๋ฒ์ด๋ ์ง๋ฃจํ ๋๋จธ์ง ์ ์ ๋๊ฐ ๊ฒ์์ ํ๊ธฐ๋ก ๊ฒฐ์ ํ๋ค. ๊ฒ์์ ์ฒซ ๋ฒ์งธ ๋ผ์ด๋์์ ์๋ฒ์ด๋ ์์คํค๋ฅผ ํ ์ ๋ค์ดํค๊ณ , ๋ฌ๋ ค๊ฐ๋ฉฐ ๊ฐ์ฅ์ ํ ๊ฐ์ฉ ๋ชจ๋ ์ฐ๋ค. ๊ทธ ๋ค์ ๋ผ์ด๋์์๋ 2, 4, 6, ... ๋ฒ ๋ฐฉ์ ๋ค์ ์ ๊ทธ๊ณ , ์ธ ๋ฒ์งธ ๋ผ์ด๋์์๋ 3, 6, 9, ... ๋ฒ ๋ฐฉ์ด ์ด๋ ค์์ผ๋ฉด ์ ๊ทธ๊ณ
www.acmicpc.net
๋ฌธ์
n๊ฐ์ ๋ฐฉ์ด ์ผ๋ ฌ๋ก ๋์ด์ ๊ฐ์ฅ์ด ์๋ค. ๊ฐ ๋ฐฉ์๋ ๋ฒ์ ์ ๋ง์ด ๋ฐ์ ํ์์ด ๊ตฌ๊ธ๋์ด์๋ค.
์ฒซ ๋ฒ์งธ ๋ผ์ด๋์์ ์๋ฒ์ด๋ ๋ชจ๋ ๊ฐ์ฅ์ ํ ๊ฐ์ฉ ๋ชจ๋ ์ฐ๋ค. ๊ทธ ๋ค์ ๋ผ์ด๋์์๋ 2, 4, 6, ... ๋ฒ ๋ฐฉ์ ๋ค์ ์ ๊ณก, ์ธ ๋ฒ์งธ ๋ผ์ด๋์์๋ 3, 6, 9, ... ๋ฒ ๋ฐฉ์ด ์ด๋ ค์์ผ๋ฉด ์ ๊ทธ๊ณ , ์ ๊ฒจ์๋ค๋ฉด ์ฐ๋ค. k๋ฒ์งธ ๋ผ์ด๋์์๋ ๋ฒํธ๊ฐ k์ ๋ฐฐ์์ธ ๋ฐฉ์ด ์ด๋ ค ์์ผ๋ฉด ์ ๊ทธ๊ณ , ์ ๊ฒจ ์๋ค๋ฉด ์ฐ๋ค. ์ด๋ ๊ฒ n๋ฒ์งธ ๋ผ์ด๋๊น์ง ์งํํ ์ดํ, ์๋ฒ์ด๋ ์์คํค์ ๋ง์ง๋ง ๋ณ์ ๋ง์๊ณ ์ฐ๋ฌ์ ธ ์ ๋ ๋ค.
๊ตฌ๊ธ๋์ด์๋ ๋ช ๋ช (์ด์ฉ๋ฉด 0๋ช )์ ํ์๋ค์ ์์ ์ ๋ฐฉ์ ์ ๊ทธ์ง ์์ ์ฑ ์๋ฒ์ด๊ฐ ์ฐ๋ฌ์ ธ๋ฒ๋ ธ๋จ ๊ฒ์ ๊นจ๋ซ๊ณ ์ฆ์ ๋๋ง์น๋ค.
๋ฐฉ์ ๊ฐ์๊ฐ ์ฃผ์ด์ก์ ๋, ๋ช ๋ช ์ ํ์๋ค์ด ๋์ฃผํ ์ ์๋์ง ์์๋ณด์.
์ ๋ ฅ
์ ๋ ฅ์ ์ฒซ ๋ฒ์งธ ์ค์๋ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ T๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค๋ ํ ์ค์ ํ ๊ฐ์ฉ ๋ฐฉ์ ๊ฐ์ n(5 โค n โค 100)์ด ์ฃผ์ด์ง๋ค.
๋ฉ๋ชจ๋ฆฌ | ์๊ฐ |
1999 KB | 0 ms |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int t, n, ans;
int prison[105];
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 2; i <= n; i++) {
for (int j = i; j <= n; j += i) {
prison[j] = prison[j] ? 0 : 1;
}
}
for (int i = 1; i <= n; i++) {
if (!prison[i]) ans++;
}
printf("%d\n", ans);
ans = 0;
memset(prison, 0, sizeof(prison));
}
return 0;
}
|
cs |
๋ ์์ค์น
์ข ๋ง ์๊ฐํ๋ฉด ์ด๋ ๊ฒ ๋์จ๋ต๋๋ค ^^.. ๋ฃจํธ ๊ฐ์ด๋ค..... ์ด ๋ถ๋ถ์ ๋ค์ ์ฃผ ์คํฐ๋ ํ ๋ ์๋
ผํ๊ธฐ..
1
2
3
4
5
6
7
8
9
10
|
#include<stdio.h>
int main() {
int i, t, n; scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (i = 1; i*i <= n; i++);
printf("%d\n", i-1);
}
return 0;
}
|
cs |
'๐ฅ PS(Problem Solving) ๐ฅ > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] #3190 ๋ฑ (0) | 2019.09.29 |
---|---|
[BOJ] #16929 Two Dots (0) | 2019.09.29 |
[BOJ] #14501 ํด์ฌ (0) | 2019.09.19 |
[BOJ] #2309 ์ผ๊ณฑ ๋์์ด (0) | 2019.09.19 |
[BOJ] #14888 ์ฐ์ฐ์ ๋ผ์๋ฃ๊ธฐ (0) | 2019.09.04 |
๋๊ธ