[Python] 백준/BOJ 6219번: 소수의 자격 (Silver 3)

💻 Problem

문제 보러 가기

 

농부 존은 소들에게 소수로 차례차례 번호를 매기는 중이다. 베시는 이 번호에서 숫자 D가 몇 번이나 등장하는지 궁금해졌다.

베시를 도와 범위 A..B(A와 B 포함)내에서 숫자 D를 포함하는 소수의 개수를 구해보자.

소수는 두개의 자연수(1과 자기 자신)로만 나누어 떨어지는 자연수를 말한다. 소수의 예로는 2,3,5,7,11,13,17,19,23,29.. 가 있다.

• 1 ≤ A ≤ B ≤ 4,000,000
• B ≤ A + 2,000,000

 

💡 Approach

처음엔 그냥 반복문으로 단순하게 소수 구하는 방법으로 풀었더니 1%에서 시간초과 떴다.

import sys
input = sys.stdin.readline

def is_include(n):
    if str(D) in str(n):
        return True
    return False

def is_demical(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

A, B, D = map(int, input().split())
cnt = 0

for i in range(A, B + 1):
    if is_demical(i) and is_include(i):
        cnt += 1

print(cnt)

위처럼 풀면 시간복잡도가 O((B - A) * √ B)이다.

B의 최댓값은 4 * 10^6, A의 최댓값은 2 * 10^6이다.

계산하면 4 * 10^9으로 2초를 초과하는 게 맞다..

 

그렇다면 에라토스테네스의 체로 풀어야짓..

아직 못 외웠는데 담엔 진짜 외우자???!!

 

이전에 소수 문제 풀었던 거 책갈피

• i 반복문 범위가 int(B ** 0.5)인 이유
• 에라토스테네스의 체 동작 방식

 

✏️ Solution

import sys
input = sys.stdin.readline

A, B, D = map(int, input().split())
sieve = [1] * (B + 1) # 숫자가 지워졌는지 여부를 나타내는 체

for i in range(2, int(B ** 0.5) + 1):
    # 아직 지워지지 않은 경우
    if sieve[i]:
        # i의 배수를 모두 제거
        for j in range(i * i, B + 1, i):
            if sieve[j]:
                sieve[j] = 0

for i in range(A, B + 1):
    if sieve[i] and str(D) not in str(i):
        sieve[i] = 0

print(sum(sieve[A:]))

에라토스테네스의 체 시간복잡도는 O(n log log n)이다.

 

j 반복문에서 범위가 i * i가 시작하는 이유는 다음과 같다.

처음엔 i로 시작했는데 이러면 자기 자신을 지워버려서 안 된다.

 

그래서 2 * i로 하려고 했는데 다른 사람 코드를 보니 i * i로 하고 있었다.

물론 2 * i도 맞긴 하지만.. 왜 i * i도 되는 거지?? 생각해 봤다.

어차피 i * (i - 1)까지는 이전 검사에서 지워진다.. 그래서 i * i부터 해도 된다.

 

예를 들어, i = 3이면 3, 6, 9, ... 순일 텐데

3은 자기 자신이라 지우면 안 되고 6은 이미 2의 배수 검사할 때 지워졌을 것이다.

그래서 9부터 해도 된다.

 

예를 들어, i = 5면 5, 10, 15, 20, 25, ... 순일 텐데

5는 자기 자신이라 지우면 안 되고 10, 15, 20은 이미 2의 배수나 3의 배수를 검사할 때 지워졌을 것이다.

그래서 25부터 시작해도 된다.

 

예를 들어, i = 11이면 11, 22, 33, 44, 55, 66, 77, 88, 99, 121, ... 순일 텐데

11은 자기 자신이라 지우면 안 되고 22 ~ 99까지는 각각 2, 3, 4, 5, 6, 7, 8, 9의 배수를 검사할 때 지워졌을 것이다.

그래서 121부터 시작해도 된다.

 

즉, i * (i - 1)까지는 이미 이전 검사에서 지워지니 i * i부터 시작해도 되는 것이다.