[백준 / 소수] 1456 : 거의 소수 (python)

문제 설명

문제

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.

두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

입력

첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다.

출력

첫째 줄에 총 몇 개가 있는지 출력한다.

제한

• 1 ≤ A ≤ B ≤ 10^14

예제 입력 1

1 1000

예제 출력 1

25

예제 입력 2

1 10

예제 출력 2

3

예제 입력 3

5324 894739

예제 출력 3

183

풀이

import math

A, B = map(int, input().split())
arr = [0] * (int(math.sqrt(B))+1)
cnt = 0

for i in range(len(arr)):
    arr[i] = i

for i in range(2, int(math.sqrt(len(arr))) + 1): # 얘도 +1 필수
    if arr[i] == 0:
        continue
    for j in range(i+i, len(arr), i): # math.sqrt(B) 까지만 해서 자꾸 오류났음. math.sqrt(B) + 1을 하든지 len(arr)을 해야함.
        arr[j] = 0

for i in range(2, len(arr)):
    if arr[i] != 0:
        temp = i * i
        while temp <= B:
            if temp < A:
                temp *= i
                continue
            temp *= i
            cnt += 1

print(cnt)

 

• A와 B 사이의 거의 소수를 구하려면, A의 제곱근 ~ B의 제곱근 사이에 있는 소수를 구하고 이 소수의 거의 소수를 구하면 된다.
• 에라토스테네스의 체를 이용하여 A의 제곱근 ~ B의 제곱근 사이에 있는 소수를 구했다.
  바깥 반복문은 제곱근까지만 검사하면 되므로 B 제곱근의 제곱근까지만 검사하면 된다.