[백준, BOJ] 9753 - 짝 곱

1. Question

정수 K (1 ≤ K ≤ 100,000)가 주어진다. 이때, K보다 크거나 같은 서로 다른 소수의 곱 중에서 가장 작은 곱을 찾는 프로그램을 작성하시오.

1.1 Input

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 20)이 주어진다. 다음 T개 줄에는 K가 한 줄에 하나씩 주어진다. 

1.2 Output

각각의 K마다 K보다 크거나 같은 서로 다른 두 소수의 곱 중에서 가장 작은 곱을 출력한다.

1.3 Example

입력	출력
5 1 3 10 300 100000	6 6 10 301 100001

2. Approach

심플하게 이해하기 좋은 문제다.

$k$가 주어지면 두 소수 $a,b$에 대해 $k \le ab$를 만족하는 $ab$의 최소값을 출력해야한다.

쿼리가 적긴하지만 없는 편은 아니어서 에라토스테네스의 체를 이용해서 100000까지의 소수를 모두 구한다.

에라토스테네스의 시간복잡도가 $O(n \; loglog\; n)$으로 알려져 있으므로, 100000은 충분히 커버가능하다.

그 다음부터는 간단하다.

$k$가 $p$로 나눠지고 $k$를 $p$로 나눈 몫이 다시 소수인지 판단하면된다.

다만 $a$와 $b$가 서로다른 소수이므로 $k$를 $p$로 나눈 몫이 $p$와 같으면 안된다.

아니라면 k++해주고 다시 찾으면 끝.

$n$이하의 소수의 개수는 ${n \over log n}$으로 수렴한다는 사실 (소수정리)이 알려져있고 , $n$과 $2n$사이에 적어도 하나의 소수가 존재한다는 사실 (베르트랑 공준)이 알려져 있으므로, 코드의 복잡도는 $O({n^2 \over log \; n})$이다.

 

3. Submission

4. Code

import math

def getPrimes(n):
    is_prime = [False, False] + [True] * (n - 1)
    max_len = int(math.sqrt(n))
    
    for i in range(2, max_len):
        if is_prime[i]:
            for j in range(2*i, n, i):
                is_prime[j] = False
    
    return [i for i in range(2, n) if is_prime[i]]

list_primes = getPrimes(100000)
set_primes = set(list_primes)

N = int(input())

for _ in range(N):
    num = int(input())
    ans = 0
        
    while ans == 0:
        if not num in set_primes:
            for p in list_primes:
                
                div = num // p
                if num % p == 0 and (div in set_primes) and (div != p):
                    ans = num
                    break
        num += 1
    print(ans)