[Swift]LeetCode866.回文素数|PrimePalindrome

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10596862.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Find the smallest prime palindrome greater than or equal to N.

Recall that a number is prime if it's only divisors are 1 and itself, and it is greater than 1.

For example, 2,3,5,7,11 and 13 are primes.

Recall that a number is a palindrome if it reads the same from left to right as it does from right to left.

For example, 12321 is a palindrome.

Example 1:

Input: 6
Output: 7

Example 2:

Input: 8
Output: 11

Example 3:

Input: 13
Output: 101

Note:

1 <= N <= 10^8
The answer is guaranteed to exist and be less than 2 * 10^8.

求出大于或等于 N 的最小回文素数。

回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数。

例如，2，3，5，7，11 以及 13 是素数。

回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是回文数。

例如，12321 是回文数。

示例 1：

输入：6
输出：7

示例 2：

输入：8
输出：11

示例 3：

输入：13
输出：101

提示：

1 <= N <= 10^8
答案肯定存在，且小于 2 * 10^8。

Runtime: 160 ms

Memory Usage: 19.4 MB

 1 class Solution {
 2     func primePalindrome(_ N: Int) -> Int {
 3         if N < 10{
 4             let resDic = [2,2,2,3,5,5,7,7,11,11]
 5             return resDic[N]
 6         }
 7         let s = String(N)
 8         var half = Int(s.prefix(s.count/2)) ?? 1
 9         var hasMidHandle = s.count % 2 == 1
10 
11         while 1==1 {
12             let maxHalf = maxHalf9(half)
13             if !hasMidHandle {
14                 for h in half...maxHalf{
15                     let tail = String(String(h).reversed())
16                     let num = Int(String(h)+tail) ?? 1
17                     if num < N {    continue    }
18                     if isPrimer(num){
19                         return num
20                     }
21                 }
22                 hasMidHandle = true
23                 half = (maxHalf + 1) / 10
24             }
25             for h in half...maxHalf{
26                 let tail = String(String(h).reversed())
27                 for m in 0...9{
28                     let num = Int(String(format: "%d%d",h,m)+tail) ?? 1
29                     if num < N {    continue    }
30                     if isPrimer(num){
31                         return num
32                     }
33                 }
34             }
35             hasMidHandle = false
36             half = maxHalf + 1
37         }
38     }
39 
40     // 123 -> 999
41     func maxHalf9(_ num:Int) -> Int {
42         var n = 1
43         for _ in 0..<String(num).count{
44             n *= 10
45         }
46         return n-1
47     }
48 
49     func isPrimer(_ num:Int) -> Bool{
50         if num % 2 == 0 { return false }
51         let top = Int(sqrt(Double(num)))
52         var i = 3
53         while i <= top{
54             if num % i == 0{ return false }
55             i += 2
56         }
57         return true
58     }
59 }

Runtime: 896 ms

Memory Usage: 18.6 MB

 1 class Solution {
 2     func primePalindrome(_ N: Int) -> Int {
 3         if 8 <= N && N <= 11
 4         {
 5             return 11
 6         }
 7         for x in 1..<100000
 8         {
 9             var s:String = String(x)
10             var r:String = String(s.reversed())
11             var y:Int = Int(s + r.subString(1)) ?? 0
12             if y >= N && isPrime(y) {return y}
13         }
14         return -1
15     }
16 
17     func isPrime(_ x:Int) -> Bool
18     {
19         if x < 2 || x % 2 == 0 {return x == 2}
20         var i:Int = 3
21         while(i * i <= x)
22         {
23             if x % i == 0
24             {
25                 return false
26             }
27             i += 2
28         }
29         return true
30     }
31 }
32 
33 extension String {
34     // 截取字符串：从index到结束处
35     // - Parameter index: 开始索引
36     // - Returns: 子字符串
37     func subString(_ index: Int) -> String {
38         let theIndex = self.index(self.endIndex, offsetBy: index - self.count)
39         return String(self[theIndex..<endIndex])
40     }
41 }