(Python/🥇5)백준알고리즘 1456번: 거의 소수

 

문제 바로가기 

 

백준알고리즘 거의소수

 

문제:

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

입력:

 

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

출력:

 

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

 

 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

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

board = [True] * (int(B ** 0.5) + 1)
board[1] = False
m = int(B **0.5)
for i in range(2,m+1):
    if board[i]:
        for j in range(i**2,m+1,i):
            board[j] = False

result = 0
for i in range(1, len(board)):
    if board[i]:
        res = i * i
        while True:
            if res < A:
                res *= i
                continue
            elif res > B:
                break
            res *= i
            result += 1
print(result)

 

일단 소수를 구해준다. 에라토스테네스의체 를 사용하면 된다.

주어진 숫자의 제곱근 까지 소수인지 찾고 소수가 아니라면 주어진 숫자까지 곱해주면서 소수가 아니라고 체크해 주는것이다.

 

그리고 소수를 찾으면 그 소수를 하나씩 돌면서

만약에 소수이면 제곱을 해준다. 근데 그 제곱이 시작값인 A보다 작으면 한번 더 제곱해준다 2제곱이 3제곱이 되는것이다. 하지만 이럴때는

갯수가 추가되는것은 아니니 continue로 다음 while 문이 돌게 써준다. 그러다 res > B 가 되면 break해준다.