[SWEA 코딩] 테네스의 특별한 소수 - PYTHON #4698

소스 코드

T = int(input())

# 소수 저장 배열
prime = [2]

# 소수 = 0, 소수가 아닌 수 = 1
visited = [0]*1000001

for q in range(3,1000001,2):

    # q가 소수면
    if visited[q] == 0:

        # prime에 추가
        prime.append(q)

        # q의 배수만 확인하면 됨
        for w in range(q,1000001,q):

            # 나머지가 0이면(소수가 아니면)
            if w%q == 0:

                # 체크
                visited[w] = 1

for tc in range(1,1+T):
    d,a,b = map(int,input().split())

    res = 0

    # d의 형태를 string으로 만들어서 특별한 소수 확인
    d = str(d)

    for w in prime:

        # 범위 조건
        if a <= w <= b:

            # 특별한 소수 조건
            if d in str(w):
                res += 1
        
        # w가 b보다 크면 그만두기
        # prime은 sort되어있는 상태라서 w 이상의 수는 확인할 필요 없음
        elif w > b:
            break

    print('#{} {}'.format(tc,res))

 

---

해결 방법

1. 소수를 미리 구해놓고 이를 활용하면 됨

 

2. 이를 위해서 에라토스테네스의 체를 활용하면 됨

---

느낀 점

 

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.