사용자 도구

사이트 도구


ps:problems:boj:1644

소수의 연속합

ps
링크acmicpc.net/…
출처BOJ
문제 번호1644
문제명소수의 연속합
레벨골드 3
분류

소수목록, 투 포인터

시간복잡도O(nloglogn)
인풋사이즈n<=4,000,000
사용한 언어Python
제출기록56036KB / 264ms
최고기록264ms
해결날짜2021/08/04

풀이

  • 소수들을 먼저 찾아서 리스트에 저장해두고 거기에서 합이 N이 되는 연속된 구간의 갯수를 찾으면 된다.
  • n이하의 소수들을 모두 찾는 것은 에라토스테네스의 체를 이용해서 O(nloglogn)에 가능하다.
  • 배열에서 합이 Y가 되는 구간의 갯수를 세는 것은 투 포인터를 이용하면 배열 길이에 비례하는 시간에 구할수 있다. n이하의 소수의 갯수는 O(n/logn)이므로, 이 작업의 시간복잡도는 O(n/logn)
  • 총 시간복잡도는 O(nloglogn)이 된다.

코드

"""Solution code for "BOJ 1644. 소수의 연속합".

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

Tags: [Sieve] [TwoPointer]
"""

from teflib import numtheory


def main():
    N = int(input())

    primes = numtheory.prime_list(N)
    left_iter, right_iter = iter(primes), iter(primes)
    prime_sum = answer = 0
    while True:
        try:
            if prime_sum == N:
                answer += 1
            if prime_sum <= N:
                prime_sum += next(right_iter)
            else:
                prime_sum -= next(left_iter)
        except StopIteration:
            break

    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
B K G U C
 
ps/problems/boj/1644.txt · 마지막으로 수정됨: 2022/07/23 03:09 저자 teferi