{"id":9910,"date":"2022-12-31T21:11:28","date_gmt":"2023-01-01T05:11:28","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9910"},"modified":"2022-12-31T21:15:31","modified_gmt":"2023-01-01T05:15:31","slug":"leetcode-2523-closest-prime-numbers-in-range-ep407","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/uncategorized\/leetcode-2523-closest-prime-numbers-in-range-ep407\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2523. Closest Prime Numbers in Range EP407"},"content":{"rendered":"\n<p>Given two positive integers&nbsp;<code>left<\/code>&nbsp;and&nbsp;<code>right<\/code>, find the two integers&nbsp;<code>num1<\/code>&nbsp;and&nbsp;<code>num2<\/code>&nbsp;such that:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>left &lt;= nums1 &lt; nums2 &lt;= right <\/code>.<\/li><li><code>nums1<\/code>&nbsp;and&nbsp;<code>nums2<\/code>&nbsp;are both&nbsp;<strong>prime<\/strong>&nbsp;numbers.<\/li><li><code>nums2 - nums1<\/code>&nbsp;is the&nbsp;<strong>minimum<\/strong>&nbsp;amongst all other pairs satisfying the above conditions.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>the positive integer array<\/em>&nbsp;<code>ans = [nums1, nums2]<\/code>.&nbsp;<em>If there are multiple pairs satisfying these conditions, return the one with the minimum<\/em>&nbsp;<code>nums1<\/code>&nbsp;<em>value or<\/em>&nbsp;<code>[-1, -1]<\/code>&nbsp;<em>if such numbers do not exist.<\/em><\/p>\n\n\n\n<p>A number greater than&nbsp;<code>1<\/code>&nbsp;is called&nbsp;<strong>prime<\/strong>&nbsp;if it is only divisible by&nbsp;<code>1<\/code>&nbsp;and itself.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> left = 10, right = 19\n<strong>Output:<\/strong> [11,13]\n<strong>Explanation:<\/strong> The prime numbers between 10 and 19 are 11, 13, 17, and 19.\nThe closest gap between any pair is 2, which can be achieved by [11,13] or [17,19].\nSince 11 is smaller than 17, we return the first pair.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> left = 4, right = 6\n<strong>Output:<\/strong> [-1,-1]\n<strong>Explanation:<\/strong> There exists only one prime number in the given range, so the conditions cannot be satisfied.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= left &lt;= right &lt;= 10<sup>6<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Sieve of Eratosthenes<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-full\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/12\/2523-s1.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/12\/2523-s1.png\" alt=\"\" class=\"wp-image-9912\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/12\/2523-s1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/12\/2523-s1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/12\/2523-s1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<p>Use Sieve of Eratosthenes to find all primes in range [0, right].<\/p>\n\n\n\n<p>Check neighbor primes and find the best pair.<\/p>\n\n\n\n<p>Time complexity: O(nloglogn)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<int> closestPrimes(int left, int right) {\n    vector<int> primes(right + 1, 1);\n    primes[0] = primes[1] = 0;\n    for (int i = 2; i <= sqrt(right); ++i) {      \n      if (!primes[i]) continue;      \n      for (int x = i * i; x <= right; x += i)\n        primes[x] = 0;\n    }\n    vector<int> ans{-1,-1};\n    for (int i = left, last = -1, best = INT_MAX; i <= right; ++i) {\n      if (!primes[i]) continue;\n      if (last > 0 && i - last < best) {\n        best = i - last;\n        ans = {last, i};\n      }\n      last = i;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given two positive integers&nbsp;left&nbsp;and&nbsp;right, find the two integers&nbsp;num1&nbsp;and&nbsp;num2&nbsp;such that: left &lt;= nums1 &lt; nums2 &lt;= right . nums1&nbsp;and&nbsp;nums2&nbsp;are both&nbsp;prime&nbsp;numbers. nums2 &#8211; nums1&nbsp;is the&nbsp;minimum&nbsp;amongst all other&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-9910","post","type-post","status-publish","format-standard","hentry","category-uncategorized","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9910","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9910"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9910\/revisions"}],"predecessor-version":[{"id":9914,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9910\/revisions\/9914"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9910"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9910"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9910"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}