https://www.acmicpc.net/problem/15897
15897번: 잘못 구현한 에라토스테네스의 체
성원이는 오늘 이산수학 수업 시간에 에라토스테네스의 체에 대해 배웠다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 성원이는 이 방법에 너무나 큰 감명을 받았고, 당장 실습실에 가서 C++로 구현해보기로 했다. 그런데 성원이는 교재도 없고 필기를 하는 성격도 아니기 때문에 수업내용이 정확히 기억나지 않았다. 성원이는 기억을 열심히 더듬어 마침내 아래와 같은 코드를 작성했다. 옆에 앉아있던 킹갓제너럴엠페러충무공마제
www.acmicpc.net
이거 줄여보겠다고 4시간 씀
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
ll n;
cin >> n;
ll ans = n;
n--;
ll count = n;
if (n == 0) {
cout << 1 ;
return 0;
}
for (ll i = 1; i <= sqrt(n); i++) {
ans += n / i;
if (i >= n / i)
break;
ll tem = count - n / (i+1);
count = n / (i+1);
ans += tem * i ;
}
cout << ans;
|
Color Scripter
Simple & Flexible Syntax HighLighter
colorscripter.com