[Google Kick Start] 2021 구글 킥스타트 Round B Consecutive Primes 풀이

 

 

문제

---

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435a5b/000000000077a8e6

Kick Start - Google’s Coding Competitions

 

 

나의 풀이

---

이 문제에서의 핵심은 주어진 조건 Z의 상한이 10^8인데 1~10^8까지의 소수를 모두 구할 필요가 없다는 것이다. 또한 탐색을 할 때에 sqrt(Z)부터 순차적으로 감소시키며 탐색해야 시간을 줄일 수 있다.

예컨대, 연속한 두 소수 5와 7의 곱은 35이다. 그런데 거꾸로 이 35가 어떠한 두 연속된 소수를 곱해서 나왔는지를 알아보려고 한다. 그러면 sqrt(35) = 5.xxx인데 5, 4, 3, 2 이러한 순서로 탐색을 해나아가야 한다. 다른 예시로, 연속된 두 소수 11과 13의 곱은 143이다. 거꾸로 어떤 두 연속된 소수를 곱해 143을 만들 수 있는지 탐색하려면 sqrt(143)=11.xxx이므로 11부터 10, 9, 8,... 이러한 순서로 탐색해 나가야 한다.

왜 그럴까? 핵심은 "연속된" 두 소수의 곱을 찾는 문제이므로 sqrt(Z)인 두 수를 곱해 Z가 된다면 이 때부터는 연속한 두 소수를 곱할 수가 없게 된다.

 

코드

---

# https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435a5b/000000000077a8e6

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

def CP():
    Z = int(input())
    for first in range(int(Z**0.5), 1, -1):
        if isPrime(first):
            second = first + 1
            while not isPrime(second):
                second += 1
            if first * second <= Z:
                return first * second

for t in range(int(input())):
    print(f'Case #{t+1}: ', CP())