4698. 테네스의 특별한 소수

4698. 테네스의 특별한 소수

문제 요약

테네스는 소수를 좋아한다. 소수란 1과 자기 자신만으로 나뉘어 떨어지는 숫자로 작은 것부터 나열하면 2, 3, 5, 7, 11, 13, 17, 19, 23, …같은 수들이 있다.

또한 테네스는 D를 포함하는 숫자도 좋아한다. 그렇기에 소수가 D를 포함하면 더욱 더 좋아하여 특별한 소수라고 부르기로 했다.

예를 들어 D = 3이면 3, 13, 23, … 같은 소수들이 3을 포함하였으므로 테네스는 이런 숫자들을 특별한 소수라고 부를 것이다.

D가 주어질 때, A이상 B이하의 수 중에서 특별한 소수인 것들의 개수를 구하는 프로그램을 작성하라.

문제 풀이(처음 푼 답)

에라토스테네스의 체를 이용하여 0~ 1000000까지 소수여부를 배열에 저장한다.
그 후 d가 포함 해당 숫자에 포함되어 있고 해당 숫자가 소수인지 판별한다.
이것을 코드로 나타내면 다음과 같다.

primes = [False, False] + [True for i in range(1000000)]
prime = []
for i in range(2, len(primes)):
    if primes[i]:
        prime.append(i)
        for j in range(2*i, len(primes), i):
            primes[j] = False
            
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    d, a, b = map(int, input().split(" "))
    ans = 0
    for i in range(a, b + 1):
        s = str(i)
        if (str(d)) in s and primes[i]:
            ans += 1
    print("#" + str(test_case) + " " + str(ans))

하지만 최적화를 할 수가 있다. 처음 풀었을 때에는 0~1000000까지 소수가 아닌 숫자 까지 확인을 했지만 a, b의 바운더리에서 부터 소수인 숫자만 확인하면 최적화를 할 수가 있다.
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 ....]이고 a = 10, b= 30이다. 2부터 시작하는 것이 아닌 바운더리인 11부터~ 29까지 확인해보면 된다.

문제 풀이(바이너리 서치)

1. 일단 1~ 10000000 까지 소수를 구한다.
   

2. 바이너리 서치 함수를 만든다.
   

3. 해당 바운더리에서 찾는다.
   
   start는 이상을 찾아야 하므로 해당 인덱스 + 1을 해준다.