[Python][SWEA] 4698. 테네스의 특별한 소수 D3

SW Expert Academy

---

🗒️ 파이썬 코드 풀이

lst = [i for i in range(1000001)]  # 에라토스테네스 리스트 만들기
for i in range(2,1000001) : # 2부터 시작해야 함
    for j in range(i,1000001,i): # 각 수의 배수를 0으로 변환
        if lst[j] == i : continue # i=j (해당값)은 변환 X
        lst[j] = 0

T = int(input())
for test_case in range(1, T + 1):
    D,A,B = map(int,input().split())
    cnt = 0

    for i in range(A,B+1) :
        if lst[i]!=0 and lst[i]!=1 : # 0,1은 무시
            if str(D) in str(lst[i]):
                cnt += 1
    print(f"#{test_case} {cnt}")

 

1. 에라토스테네스 리스트를 반복문 밖에서 만들어준다. 

 

2. 에라토스테네스 체를 만들때 이중 for 문을 돌리는데, 이때 i의 범위는 2부터 시작해야 한다.

( 0부터 시작하면 반복문 에러 / 1부터 시작하면 모든 값 = 0 )

 

3. 두번째 반복문에서 i의 배수만큼 반복하여, i의 배수를 0으로 만들어 준다.

 

3. lst[j] 가 i인 경우를 제외 ( 얘를 기준으로 소수를 제거하므로)

 

4. 이제 아래 반복문으로 A~B까지를 조건에 맞게 필터링 한다. (이때 0,1 은 제외 (소수가 아니므로))

 

5. 각 숫자들을 문자열로 바꿔서 비교 -> 조건에 맞으면 cnt + 1

 

📑 다른 풀이 방법

check = [0] * 1000001
prime = []
for i in range(2,len(check)):
    if check[i] == 0 : prime.append(i)
    for j in range(i,len(check),i):
        if i == j: continue
        check[j] = 1

T = int(input())
for test_case in range(1, T + 1):
    D,A,B = map(int,input().split())
    cnt = 0

    for x in prime :
        if A<=x<= B:
            if str(D) in str(x):
                cnt+=1

    print(f"#{test_case} {cnt}")

 

에라토스테네스 체를 구하는 로직은 똑같다. 

이 코드에서는 방문 리스트를 만들어 소수만 prime 리스트에 넣어주는 방식이다.

해당 i는 제외시키고 i의 배수들은 1로 방문처리 한다.  (0,1은 애초에 방문을 안하니 prime 리스트에서 제외 됨)

 

📌 주의사항

에라토스테네스 리스트를 만들때, 범위를 잘 정해줘야한다.  이게 사소한데 좀 만 잘 못 돼도 문제가 생긴다. 

 

1. 리스트를 만들때 여유롭게 1000001정도 크기로 만들어준다. (더 크게도 괜찮음)

 

2. 또한, 해당 리스트를 만들기위해 이중 반복문을 쓰는데, 여기서 꼭 2부터 시작해야한다.

 

3.  현재 i의 배수를 0으로 만들때 i는 제외시켜야 한다.

 

4. 마지막으로 0,1을 소수가 아니므로, 필터링 해준다.

 

🧐 문제 코멘트

문제 자체가 어려운게 아니라, 시간복잡도를 맞춰야해서 어렵다.

이중 for문도 잘못하다 N^2이 돼서 조심스럽다 ... 

해당 코드를 어느정도는 외워두자 !!

---

📚 문제

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

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

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

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


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 세 정수 D, A, B(1 ≤ D ≤ 9, 1 ≤ A ≤ B ≤ 106)가 공백으로 구분되어 주어진다.

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 특별한 소수의 개수를 출력한다.