사용자 도구

사이트 도구


ps:problems:boj:6219

소수의 자격

ps
링크acmicpc.net/…
출처BOJ
문제 번호6219
문제명소수의 자격
레벨실버 3
분류

정수론

시간복잡도O(nloglogn)
인풋사이즈n<=4,000,000
사용한 언어Python
제출기록53792KB / 180ms
최고기록180ms
해결날짜2022/07/23

풀이

  • 범위안의 수들 중에서 조건을 만족하는 소수를 찾는 문제.
  • 전체 범위는 크지만, 조건을 만족하는 수들만 빠르게 생성해낼수 있다면, 조건을 만족하는 수들을 먼저 만들고, 그것들에 대해서 소수 판별 (Primality Test)을 해서 소수들만 뽑는 것이 효율적이다.
  • 전체 범위가 크지 않다면, 범위 내에서 소수 목록 구하기를 먼저 하고, 그중에 조건을 만족하는 수들을 뽑는 것이 효율적이다.
  • 이 문제는 범위가 크지 않으니, 소수 목록을 먼저 구하고, 그 소수들을 조건에 만족하는를 체크해서 만족하는 것들만 출력하면 된다.
  • 소수 목록을 구하는 데에 O(nloglogn), 이렇게 구해진 O(n/logn)개의 소수들에 대해서 O(1)의 조건체크를 해주면 된다. 총 시간복잡도는 O(nloglogn + n/logn) = O(nloglogn)

코드

"""Solution code for "BOJ 6219. 소수의 자격".

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

Tags: [Sieve]
"""

from teflib import numtheory


def main():
    A, B, D = [int(x) for x in input().split()]

    d_str = str(D)
    answer = 0
    for p in numtheory.prime_list(A, B):
        if d_str in str(p):
            answer += 1

    print(answer)


if __name__ == '__main__':
    main()
teflib.numtheory.prime_list

토론

댓글을 입력하세요:
X L O M​ V
 
ps/problems/boj/6219.txt · 마지막으로 수정됨: 2022/07/23 03:29 저자 teferi