첫째로, 조화수는 에라토스테네스의 체의 시간 복잡도를 증명하기 위해서도 맞지만 조화수 꼴의 연산 횟수를 갖는 알고리즘의 시간 복잡도 검증을 위해서 추가된 태그입니다. 이 문제에서 f(x)를 에라토스테네스의 체와 비슷하게 구하는 경우 연산 횟수가 조화수가 되므로 필요하다고 생각합니다.
둘째로, (1 ~ n)까지의 합도 구간 합입니다. 따라서 누적 합 태그가 필요하다고 생각합니다.
그리고 알고리즘 태그는 백준이 아니라 solved.ac 유저 기여에 따라 자동으로 부여됩니다. 알고리즘 태그나 티어 조정 관련 건의사항은 solved.ac 디스코드에 남겨주시면 좋을 것 같아요.

adfsfsf 1년 전
본 문제에서 제시하는 알고리즘들은 다음과 같습니다.
- 수학
- 정수론
- 누적 합
- 소수 판정
- 에라토스테네스의 체
- 조화수
이들 중, 조화수는 본 문제와 전혀 관련이 없습니다.
조사를 해보니 '조화수'는 '에라토스테네스의 체'의 '시간 복잡도 검증'에 쓰입니다.
BOJ에도 이에 대한 '잘못 구현한 에라토스테네스의 체'라는 문제가 있기는 하지만 해당 내용이 본 문제에서 사용되지는 않습니다.
풀이에 혼란을 줄 수 있으니 조화수를 본 문제의 알고리즘 목록에서 지워주셨으면 합니다.
또한 '누적 합'에 대해서도 조금 의심스럽습니다.
누적 합 알고리즘은 N개의 수에 대해 '인덱스가 0인 값부터 인덱스가 i인 값까지의 합'인 N개의 합을 구하고, 이를 활용한 '구간 합'을 구하기 위한 알고리즘입니다.
이에 대해서는 '단계별로 풀어보기'에 있는 '누적 합' 알고리즘 문제들을 풀어보면 알 수 있는 사항입니다.
물론 문제에서의 g(N)이 일종의 누적 합이며, N의 값은 무작위 순서로 주어지기 때문에 큰 수가 먼저 나오고 작은 수가 나올 경우 큰 수에 대한 g(N)을 구할 때 알게 된 작은 수의 g(N)을 다시 구하는 것을 방지하려면 '누적 합'을 버리지 않아야 합니다.
하지만 본 문제에서는 '구간 합'을 필요로 하지는 않으므로 '누적 합'이 알고리즘으로서 사용되었는지에 대해서는 의문이 듭니다.
이에 대해서도 다시 검토가 필요하며, 저는 누적 합 또한 알고리즘 목록에서 지우는 것이 혼란을 방지할 수 있다고 생각합니다.