[백준] 1456번 : 거의 소수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1456번: 거의 소수

 

1. 문제 설명

2. 풀이과정

해당 문제는 최대 범위에 해당하는 모든 소수를 구해 놓고, 구한 소수들의 N제곱값이 입력된 A와 B 사이에 존재하는지 판단해 문제를 해결할 수 있다.
입력에서 주어진 범위의 최댓값 10^14의 제곱근인 10^7까지 최대로 소수를 탐색해야 하는데 에라토스테네스의 체를 이용하여 빠르게 소수를 먼저 구한다.
이후 구한 소수들의 N제곱값이 A와 B 범위 안에 존재하는지 판별해 거의 소수의 개수를 구하면 문제를 해결할 수 있다.
 
슈도코드

1. A(시작 수), B(종료 수) 입력받기
2. li(소수 리스트) 종료 수의 제곱근까지만 저장
3. for 2 ~ 종료 수의 제곱근까지 반복
   1. 소수가 아니면 넘어감
   2. for 소수의 배수값을 전체 범위까지 반복: 현재 수가 소수가 아니라고 표시
4. count(거의 소수 개수) 초기화
5. for 2 ~ 종료 수까지 반복:
   1. li 리스트에서 해당 값이 소수이면
      1. tmp = 현재 소수 제곱
      2. while (현재 소수 N제곱값 <= 종료 수):
         1. if (현재 소수 N제곱값 >= 시작 수): 거의 소수이므로 개수 증가
         2. tmp = tmp * 현재 소수 (다음 N제곱값으로 변경)
6. 정답 출력

반응형

3. 소스코드

import sys
import math

A, B = map(int, sys.stdin.readline().split())

li = list(x for x in range(int(math.sqrt(B)) + 1))

for i in range(2, int(math.sqrt(len(li)) + 1)):
    if (li[i] == 0):
        continue
    for j in range(i + i, len(li), i):
        li[j] = 0

count = 0

for i in range(2, len(li)):
    if (li[i] != 0):
        tmp = li[i] * li[i]
        while (tmp <= B):
            if (tmp >= A):
                count += 1
            tmp *= li[i]

print(count)