BOJ 1456. 거의 소수

🔎 BOJ 1456. 거의 소수 (골드5)

https://www.acmicpc.net/problem/1456

1456번: 거의 소수

💡 SOL

import sys
import math

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

# 범위 2 ~ B**(1/2)
S = 2
E = int(B ** (1/2))

# S~E까지 소수 찾기 - 에라토스테네스의 체
sosu = [i for i in range(E+1)]
sosu[1] = 0

idx = 2
while idx <= E:
    if sosu[idx] != 0:
        n = 2
        while (idx * n) <= (E/2):
            sosu[idx * n] = 0
            n += 1
    idx += 1

# A ~ B 전체 count 에서 +하면서 for문
# 중복 신경 안 써도 됨 (소수의 n승이기 때문에)
cnt = 0
for s in list(set(sosu)):
    if s != 0:
        n = math.ceil(math.log(A, s))
        if n < 2:
            n = 2
        while s ** n <= B:
            cnt += 1
            n += 1
print(cnt)

💭 TIL

...

sosu = [i for i in range(E+1)]
sosu[1] = 0

idx = 2
while idx <= E:
    if sosu[idx] != 0:
        n = 2
        while (idx * n) <= (E/2):
            sosu[idx * n] = 0
            n += 1
    idx += 1

 ...

• 범위가 주어진 경우 소수 판별 (에라토스테네스의 체)
  1. A ~ B의 범위가 주어졌을 때, 해당 범위 내의 소수를 판별하기 위해 [:B] 의 리스트를 생성
  2. s = 2 부터 x 2, x 3, x 4 … x n 하여 나온 값을 리스트에서 지움 (해당 값은 약수가 있는 수, 즉 소수가 아니기 때문)
  3. x n 한 값이 B를 초과하지 않을 때까지 반복
  4. s += 1 하여 다음 s를 처리
  5. (2 ~ 4)의 과정을 s <= (B / 2) 조건 만족 시 까지만 반복한다.