[알고리즘 문제] K가 포함된 소수 (Python / 파이썬)

문제

정수론을 공부중인 유니와 지니는 서로에게 퀴즈를 낸다.
퀴즈는 세 자연수 v, s, e로 구성되는데, s 이상 e 이하의 자연수 중 v라는 숫자가 포함되어 있으면서 소수인 수가 몇 개인지 대답해야 한다. 여기서 v는 1 이상 9 이하의 자연수, s, e는 1 이상 1,000,000 이하의 자연수고 s보다 e가 크거나 같다. 정수론과 함께 프로그래밍을 배운 유니는 이 작업을 코드로 구현할 수 있다. 유니가 할 수 있으면 당신도 할 수 있다. 구현해보자.

입력

첫째 줄에 테스트케이스의 수 T가 주어진다..
각 테스트케이스의 첫 줄에 v, s, e가 공백으로 구분되어 주어진다.
( 1 ≤ T ≤ 100 )

출력

각 테스트케이스마다 '#'과 테스트케이스의 번호, 공백을 출력한 뒤 퀴즈의 정답을 출력한다.

---

문제 풀이

s 이상 e 이하의 자연수 중 v라는 숫자가 포함되어 있으면서

소수인 수가 몇 개인지 찾는 문제 입니다. 

 

먼저, 소수를 모두 찾아주었습니다. 

그리고 s 이상 e 이하의 자연수를 하나씩 확인하며

만약 소수라면 v가 해당 수에 포함되어 있는지 

확인하도록 해주었습니다. 

 

이때, v가 해당 수에 포함되어 있는지 확인하는 방법은 두 가지가 있습니다.

1. 10으로 나눈 결과를 이용해 자리수를 하나씩 확인

2. str 함수를 이용해 v가 있는지 확인 

첫 번째 방법은 만약 456이라는 수가 있으면 10으로 나눈 나머지는 

제일 끝자리 수 6이 되고 몫은 나머지 수인 45가 됩니다.

이처럼 10으로 나눈 결과를 이용해 자리수를 하나씩 확인할 수 있습니다.

만약 v와 동일한 수가 나오면 v를 포함하고 있다는 것이므로 True를 반환해줍니다.

두 번째 방법은 456을 str함수를 이용해 문자열로 만들면 자리수를 하나씩 

확인할 수 있습니다. 따라서 v가 포함되어있는지 확인해주면 됩니다.

 

위의 과정에서 v가 포함되어 있는 수만을 count해주면 답을 출력할 수 있습니다.

---

My Code 1 - 방법 1

# 소수를 모두 찾아줌 
MAX = 1000001

check = [True] * MAX 
check[1] = False
for i in range(2, MAX):
    for j in range(i + i, MAX, i):
        check[j] = False

# v가 포함되어 있는지 확인하는 함수
def find_v(x):
    while x > 0:
        now = x % 10 # 맨 끝자리 수
        x //= 10     # 맨 끝자리 수 분리
        if now == v: # v와 같으면 True 
            return True 
    return False # v를 찾지 못했으면 False
 
for tc in range(int(input())):
    v, s, e = map(int,input().split())

    count = 0
    for i in range(s, e + 1): # s이상 e이하 자연수 중
        if check[i]:          # 소수라면
            if find_v(i):     # v가 포함되어 있는지 확인
                count += 1    # 포함되어 있다면 count  

    print('#' + str(tc + 1), end = ' ')
    print(count)

My Code 2 - 방법 2

# 소수를 모두 찾아줌 
MAX = 1000001

check = [True] * MAX 
check[1] = False
for i in range(2, MAX):
    for j in range(i + i, MAX, i):
        check[j] = False
 
for tc in range(int(input())):
    v, s, e = map(int,input().split())

    count = 0
    for i in range(s, e + 1): # s이상 e이하 자연수 중
        if check[i]:          # 소수라면
            if str(v) in str(i): # i에 v가 있는지 확인
                count += 1       # 있다면 count

    print('#' + str(tc + 1), end = ' ')
    print(count)