백준 15897 (C++) 잘못 구현한 에라토스테네스의 체

최초 업로드: 2025-09-30 07:29:30

최근 수정 시간: 2025-09-30 07:29:30

게시자: rlatjwls3333

카테고리: 백준

# [Gold II] 잘못 구현한 에라토스테네스의 체

[문제 링크](https://www.acmicpc.net/problem/15897)

## 문제 설명

성원이는 오늘 이산수학 수업 시간에 에라토스테네스의 체에 대해 배웠다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 성원이는 이 방법에 너무나 큰 감명을 받았고, 당장 실습실에 가서 C++로 구현해보기로 했다. 그런데 성원이는 교재도 없고 필기를 하는 성격도 아니기 때문에 수업내용이 정확히 기억나지 않았다. 성원이는 기억을 열심히 더듬어 마침내 아래와 같은 코드를 작성했다.

옆에 앉아있던 킹갓제너럴엠페러충무공마제스티알고리즘마스터 형석이는 성원이의 이 코드를 보고 실소를 금할 수 없었다. 아니 대체 세상에 어떤 사람이 이딴 코드를 짠단 말이지? 형석이는 신이 나서 성원이에게 이 코드의 문제점을 마구 지적했다.

<blockquote>
형석 : 야 성원! 이거 알고리즘이 완전히 틀렸잖아! 여긴 이렇게저렇게 고쳐야지! 
성원 : 아 그렇구나... 알려줘서 정말 고마워. 
형석 : 게다가 이 코드는 수행시간도 더럽게 오래 걸리겠네. 
성원 : 그래? 내가 관심법으로 보면 왠지 $O(n)$에 돌아갈 것처럼 생겼는데? 
형석 : $O(n)$은 무슨 말도 안되는 소리야? 자 이거 봐. 수식을 이렇게저렇게 쓰면... 
형석 : 어라? 시간복잡도 증명이 잘 안 되네. 수학 공부를 너무 오랫동안 안 해서 그런가? 
성원 : IOI 금메달 킹갓제너럴알고리즘마스터도 이럴 때가 있구나. 
형석 : 시끄러! 그렇다면 내가 직접 연산횟수를 측정해서 $O(n)$이 아님을 보여주지.
</blockquote>

형석이는 위 코드의 연산횟수를 직접 측정해서 위 코드의 시간복잡도가 $O(n)$이 아님을 증명하려고 한다. 구체적으로 위 코드의 6번 줄이 몇 번 실행될지를 측정하고 그 데이터로 그래프를 그려 보여주려고 한다. 그런데 막상 직접 측정하려고 보니 이것은 매우 귀찮은 일이었다. 허접인 성원이때문에 내가 이 고생을 해야 한다니! 귀찮아진 형석이는 이 작업을 당신에게 떠넘겼다. 위 코드에서 n에 해당하는 값이 주어졌을 때, 위 코드의 6번 줄이 몇 번 실행될지를 계산하는 프로그램을 작성해서 형석이를 도와주자.

## 입력

첫 번째 줄에 위 프로그램의 입력 n의 값이 자연수로 주어진다. (1 ≤ n ≤ 109)

## 출력

첫 번째 줄에 위 프로그램의 6번 줄의 실행횟수를 출력한다.

## 풀이
n + ∑(n-1)/i 의 값을 구하는 문제로 변형시켜 풀었습니다. 이 때, n/i가 같은 값은 한번에 건너뛰는 아이디어를 사용했습니다. n/i가 같은 값들은 최대 √N개가 등장한다는 사실을 알아야 합니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    ll n; cin >> n;

ll cnt=n;
 n--;
 for(ll i=1;i<=n;) {
 ll next = n/(n/i);
 if(i==next) next++;
 cnt += (next-i)*(n/i);
 i=next;
 }
 cout << cnt;
}
```