[알고리즘] 백준 1124번 언더프라임 python - 소수, 수학적 사고력
📐

[알고리즘] 백준 1124번 언더프라임 python - 소수, 수학적 사고력

Created
2022/08/07
Tags
Algorithm
Python
Prime Number
Eratosthenes Sieve
 
2022-08-07 @이영훈
 
 

접근방법

소수를 다루는 문제입니다.
입력중에서 더 큰 정수까지의 모든 소수를 구한 뒤에 → 에라토스테네스의 체를 이용
언더프라임을 계산하려는 정수를 위에서 구해진 소수들로 나누어지는 개수를 세아립니다.
나누어진 개수가 소수인지 확인합니다.
 

파이썬 코드

Python
from typing import List

a, b = map(int, input().split())


def eratosthenes_sieve(n: int) -> List[int]:
    sieve = [True] * (n + 1)
    sieve[0] = False
    sieve[1] = False

    until = int(n ** 0.5)
    for i in range(until + 1):
        if sieve[i] is True:
            for j in range(i + i, n + 1, i):
                sieve[j] = False

    return [i for i in range(n + 1) if sieve[i] is True]


def is_prime(number: int) -> bool:
    if number == 1:
        return False

    until = int(number ** 0.5)
    for i in range(2, until + 1):
        if number % i == 0:
            return False
    return True


def is_under_prime(prime_numbers: List[int], number: int) -> bool:
    count = 0
    for prime in prime_numbers:
        if number == 1:
            break

        while number % prime == 0:
            count += 1
            number //= prime

    return is_prime(count)


prime_numbers = eratosthenes_sieve(b)

answer = 0
for i in range(a, b + 1):
    if is_under_prime(prime_numbers, i):
        answer += 1

print(answer)