[백준 15897] 잘못 구현한 에라토스테네스의 체 [C]

백준 - 15897

---

풀이

6번 줄의 실행 횟수에 따른 결과는 다음과 같다.

i	j	sum
1	1 2 3 4 5 6 7 8 9 10 11 12	12
2	1 3 5 7 9 11	6
3	1 4 7 10	4
4	1 5 9	3
5	1 6 11	3
6	1 7	2
7	1 8	2
8	1 9	2
9	1 10	2
10	1 11	2
11	1 12	2
12	1	1

일반적으로 1~n까지의 수에 대해서 sum += (n-1)/i + 1이 성립한다.

하지만 시간초과가 발생하므로 모든 수에 대해 확인하지 않고, n의 약수에 대해서만 확인하는 방법이 필요했다.

 

n의 약수(prime)에 대응하는 개수(temp)는 다음과 같이 구할 수 있다.

for (int i = 2, temp; i < n; i = temp+1)
    temp = (n-1) / ((n-1)/i);

---

소스코드

#include <stdio.h>
int main(){
    int n;
    scanf("%d", &n);
    long long sum = n;
    for (int i = 2, temp; i < n; i = temp+1){
        int prime = (n - 1)/i + 1;
        temp = (n-1) / ((n-1)/i);
        sum += prime*(temp -i +1);
    }
    printf("%lld", sum + (n > 1 ? 1 : 0));
}

---

출처 및 참고자료

15897번: 잘못 구현한 에라토스테네스의 체

Harmonic-Lemma