사용자 도구

사이트 도구


ps:problems:boj:15897

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

ps
링크https://www.acmicpc.net/problem/15897
출처BOJ
문제 번호15897
문제명잘못 구현한 에라토스테네스의 체
레벨골드 3
분류

정수론

시간복잡도O(sqrt(n))
인풋사이즈n<=10^9
사용한 언어Python
제출기록31312KB / 68ms
최고기록64ms
해결날짜2021/06/09

풀이

  • 소스코드를 훑어보면 각 i에 대해서, 6번줄의 실행횟수는 1 + (n-1)/i 가 된다는 것을 확인할 수 있다.
  • 따라서 전체 실행 횟수는, m=n-1이라고 썼을때, n + ([m/1] + [m/2] + … [m/m]) 이 된다.
  • 이것은 [N/1]+[N/2]+...+[N/N] 을 계산의 공식을 활용해서 O(sqrt(n))에 계산 가능하다. 자세한 것은 링크 참고.

코드

"""Solution code for "BOJ 15897. 잘못 구현한 에라토스테네스의 체".

- Problem link: https://www.acmicpc.net/problem/15897
- Solution link: http://www.teferi.net/ps/problems/boj/15897
"""

import math


def main():
    N = int(input())
    num = N - 1
    sqrt = math.isqrt(num)
    answer = 2 * sum(num // i for i in range(1, sqrt + 1)) - sqrt * sqrt
    print(answer + N)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Q D J J B
 
ps/problems/boj/15897.txt · 마지막으로 수정됨: 2021/06/09 15:32 저자 teferi