연속하는 두 소수 차이는 생각보다 크지 않다(prime gap)

https://en.wikipedia.org/wiki/Prime_gap

Prime gap - Wikipedia

 

1. 문제

 

23005번: Consecutive Primes (acmicpc.net)

23005번: Consecutive Primes

 

2. 풀이

 

연속하는 두 소수의 곱 $p_{n} * p_{n+1}$이 z보다 작거나 같은 최댓값을 구하는 문제

 

여기서 z의 범위가 $10^{18}$까지라서, $p_{n}$은 최대 $10^{9}$까지 필요한데,

 

에라토스테네스의 체로 $10^{9}$까지 소수를 모두 구하고, 이분탐색으로 찾아봤는데 안되더라

 

단순한 체로 구하면 메모리 초과나고, 비트마스크 체로 구하면 시간초과나더라

 

근데 prime gap이라는 개념이 있더라고

 

$g(n) = p_{n+1} - p_{n}$

 

여기서 $10^{9}$이내의 소수는 연속하는 두 소수의 차이 최댓값이 282라고 한다

 

 

 

따라서, 1) z가 주어질때 z의 제곱근을 구하고 이것보다 작거나 같은 소수 p1을 하나 찾아본다

 

어차피 커봐야 차이가 282니까 생각보다 빠르게 찾을 수 있다

 

2) 그리고 p1보다 한단계 큰 소수 p2를 찾고, p1보다 한단계 작은 소수 p3를 찾는다

 

3) p1*p2가 z보다 작거나 같으면 p1*p2가 정답이고, 그렇지 않으면 p1*p3가 정답이 된다

 

$n = 10^{9}$이내의 소수를 $O(\sqrt{N})$ 소수판정으로 해도 10000번정도 연산을 많아야 282번 안에 하나씩 찾을 수 있으니까,

 

최대 $N = 10^{18}$이지만, $O(N^{1/4})$가 되어 생각보다 빠르게 정답을 찾을 수 있다  

 

#prime gap

from sys import stdin

def is_prime(n):
    
    if n == 1:
        
        return False
    
    else:
        
        for i in range(2,int((n+1)**(1/2))+1):
            
            if n % i == 0:
                
                return False
        
        return True

#연속하는 두 소수의 차이는 10^9내에서 최대 282이다.

T = int(stdin.readline())

for i in range(1,T+1):
    
    z = int(stdin.readline())

    z_root = int(z**(1/2))

    for j in range(z_root,-1,-1):
        
        if is_prime(j) == True:
            
            p1 = j
            break
    
    for j in range(p1+1,10**9+283):
        
        if is_prime(j) == True:
            
            p2 = j
            break
    
    for j in range(p1-1,-1,-1):
        
        if is_prime(j) == True:
            
            p3 = j
            break
    
    r1 = p1*p2
    r2 = p1*p3

    if r1 <= z:

        print(f"Case #{i}: {r1}")
    
    else:
        
        print(f"Case #{i}: {r2}")

 

여기서 조심할 점은 $10^{9}$보다 작은 소수가 아니라 이보다 큰 소수가 필요할 수도 있다는 점이다.

 

$10^{9}$보다 작은 소수와 $10^{9}$보다 큰 소수의 곱이 $10^{18}$보다 작거나 같을 수 있기 때문