[LeetCode] 2523. Closest Prime Numbers in Range (Python)

 

 

난이도: Medium

Problem Description

---

Given two positive integers left and right, find the two integers num1 and num2 such that:

• left <= num1 < num2 <= right .
• Both num1 and num2 are prime numbers.
• num2 - num1 is the minimum amongst all other pairs satisfying the above conditions.

Return the positive integer array ans = [num1, num2]. If there are multiple pairs satisfying these conditions, return the one with the smallest num1 value. If no such numbers exist, return [-1, -1].

 

Problem Example

---

Example 1:

Input: left = 10, right = 19
Output: [11,13]
Explanation: The prime numbers between 10 and 19 are 11, 13, 17, and 19.
The closest gap between any pair is 2, which can be achieved by [11,13] or [17,19].
Since 11 is smaller than 17, we return the first pair.

Example 2:

Input: left = 4, right = 6
Output: [-1,-1]
Explanation: There exists only one prime number in the given range, so the conditions cannot be satisfied.

 

Constraints

---

• 1 <= left <= right <= 106

 

✏️ Solution

---

class Solution:
    def closestPrimes(self, left: int, right: int) -> List[int]:
        def make_prime_num(left, n):
            prime = [True] * (n+1)
            prime[0] = False
            if n > 0:
                prime[1] = False
            for i in range(2, int(math.sqrt(n)) + 1):
                if prime[i]:
                    j=2
                    for j in range(i * i, n + 1, i):
                        prime[j] = False

            return [i for i in range(left, right + 1) if prime[i]]

        prime = make_prime_num(left, right)
        print(prime)
        if len(prime) < 2:
            return [-1, -1]
        
        answer = [left-1, right+1]
        for i in range(len(prime)-1):
            if prime[i+1] - prime[i] < answer[1] - answer[0]:
                answer[0] = prime[i]
                answer[1] = prime[i+1] 

        return answer

 

에라토스테네스의 체를 사용하여 문제를 해결했다.

 

먼저 1부터 right까지의 수에서 소수를 찾아 left와 right 사이에 존재하는 소수를 따로 저장했다.

예를 들어 left = 10, right  = 19이면 [11, 13, 17, 19]로 저장된다.

 

이 때 left와 right 사이에 존재하는 소수의 수가 없거나 1개라면 [-1, -1]을 return 하였다.

 

소수의 수가 2개 이상이라면 현재 요소와 다음 요소의 차를 구해 answer[1] - answer[0]과 비교하여 answer 값들을 업데이트 해나갔다.

 

예를 들어 left = 10, right = 19이면 [11, 13, 17, 19]를 얻을 수 있다.

처음에 answer를 =[left-1, right+1] 즉 [9, 20]으로 설정한다.

 

모든 소수 요소에 대해 다음 요소와 차를 구한다.

현재 요소가 11일 때 다음 요소는 13이다.

13-11 = `2` < 20 - 9 = `11`이기 때문에 answer[0]과 answer[1]에 11과 13을 저장한다.

 

다음으로 넘어가 13과 17에 대해 차이를 구하고 answer의 요소의 차이와 비교하면 17 - 13 = `5` > 13 - 11 = `2`이기 때문에 넘어간다.

 

다음으로 넘어가 17과 19에 대해 차이를 구하고 answer의 요소의 차이와 비교하면 19-17 = '2' = 13-11='2'로 같다.

 

하지만 문제에서 답이 여러개이면 answer[0]의 요소가 더 작은 것을 구하라고 했다. 따라서, 17 > 11이기 때문에 넘어간다.

19 다음의 요소는 없기 때문에 반복문을 종료한다.

 

마지막으로 이러한 answer를 return 하여 정답을 맞을 수 있었다.

 

⚙️ Runtime & Memory

---

 

성능이 다른 사람들에 비해 낮긴 하다..

 

---

문제: 2523. Closest Prime Numbers in Range

 

깃허브: github

algorithmPractice/LeetCode/2610-closest-prime-numbers-in-range at main · laewonJeong/algorithmPractice