파이썬의 자료구조 - 정수론 문제풀이

정수론 알고리즘 문제풀이 (백준 온라인 저지 1456번)

거의 소수 -> 소수의 N 제곱
이 소수들을 잘 거듭제곱해보면서 a <= i^n <= b인 수의 개수를 직접 세주는 방식
10^7이하의 소수만 찾아서 계산하면 된다.
숫자를 for문을 통해 반복하면 i * i 가 Min보다 작거나 같으면 i를 계속 곱하고
Min과 Max사이에 있는 i^k 꼴을 찾을 수 있다.

import math
Min, Max = map(int,input().split()) # 최대값, 최솟값 세팅
A = [0] * (10000001) # 10,000,000안에 존재하는 모든 소수 나열

for i in range(2, len(A)) : # 각각 소수에 값 세팅
    A[i] = i 

for i in range(2, int(math.sqrt(len(A)) + 1)) :
    if A[i] == 0 : # 소수인지 확인
        continue
    for j in range(i + i, len(A), i) : # 현재 수가 소수가 아닐때 표시
        A[j] = 0

count = 0

for i in range(2, 1000001) :
    if A[i] != 0 : # 소수인 값을 찾음
        temp = A[i] # 현재 소수 설정
        while A[i] <= Max / temp:
            if A[i] >= Min / temp : # 범위 내에 있을때
                count += 1 # 정답값을 증가
            temp = temp * A[i]


print(count)