★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：为敢（WeiGanTechnologies）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10777313.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
公元2019年4月1日，时值西方愚人节，互联网激流暗涌，网络大佬各领风骚。然而从Internet某个小角落，一个征婚热帖撩动了广大单身攻城狮、程序猿、码农的热血激情。而今暗流退下，且让我们重新回味，整理一番。
如你，猜测这是新出炉的高智商诈骗剧本？或者认为是某某互联网HR大佬招兵买马的钓鱼问题？就像你在百度首页按下[F12]，映入眼帘的招聘文字。但我们眼中只看到算法问题，微信号是我们是特别不关心的事情。这个征婚正文比较影响你的关注点，我现在马上提炼出具体的问题：
问题1：求乘积为[7140229933]的两个质数？
问题2：求乘积为[6541367***]的两个质数？
问题1思路历程：
质数（prime number）定义：在大于1的自然数中，只能被自身或1整除的数即为质数。质数又称素数，质数有无限多个。
(1)、我们先用埃拉托色尼筛选法求出指定范围的质数集合。
埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.～194B.C.)提出的一种筛选法。 是针对自然数列中的自然数而实施的，用于求一定范围内的质数，它的容斥原理之完备性条件是p=H~。
埃氏筛法步骤：
(a).先把1删除（1既不是质数也不是合数）
(b).读取队列中当前最小的数2，然后把2的倍数删去
(c).读取队列中当前最小的数3，然后把3的倍数删去
(d).读取队列中当前最小的数5，然后把5的倍数删去
(e).读取队列中当前最小的数7，然后把7的倍数删去
(f).如上所述直到需求的范围内所有的数均删除或读取
注意：此处的队列并非数据结构队列，如需保留运算结果，处于存储空间的充分利用以及大量删除操作的实施，建议采用链表的数据结构。
(2)、有了质数集合，两数之积这个问题是不是有一点眼熟呢？
正在美帝田纳西求学的大神级前辈Grandyang告诉我们：平生不识TwoSum，刷尽LeetCode也枉然。。。。。
因为7140229933是10位数，每个因数平均是5位。所以我们可以选择筛选出十万范围内的质数，只需一次通过哈希表，尝试求出这两个质数（理工女同学的微信号）。并且我们把求质数的范围作为一个参数，如果十万范围里面求不出结果，我们可以扩大筛选范围。
Talk is cheap.Show me your code.多说无用，看我行动。
1 import Foundation
2 class Solution {
3 func findBeauty(_ number:Int, _ target: Int) -> String {
4 var primes = Set(2...number)
5 //埃拉托色尼筛选法
6 (2...Int(sqrt(Double(number)))).forEach {
7 let _ = primes.subtract(stride(from: 2*$0, through: number, by: $0))
8 }
9 //转换为Double
10 let nums:[Double] = Array(primes).map{Double($0)}
11 var table:[Double:Double] = [Double:Double]()
12 for (firstIndex, num) in nums.enumerated() {
13 let res: Double = Double(target) / Double(num)
14 //可选链接
15 if table[res] == nil
16 {
17 table[num] = Double(firstIndex)
18 }
19 else
20 {
21 //转换为Int
22 let res:Int = Int(res)
23 let num:Int = Int(num)
24 print(res)
25 print(num)
26 let str:String = res > num ? (String(num) + String(res)) : String(res) + String(num)
27 return "Lin" + str
28 }
29 }
30 return String()
31 }
32 }
点击：Playground测试
1 //测试
2 print(Solution().findBeauty(100000, 7140229933))
3 //Print 85229
4 //Print 83777
5 //Print Lin8377785229
注意：已经输出女同学的微信号。但是你搜索之后会发现，这只是个小号。认真看完第2问，文章末尾告诉你常用微信号。
问题2思路历程：
我们同样用埃拉托色尼筛选法求出指定范围的质数集合。积为10位数，每个因数平均是5位。所以我们筛选出十万范围内的质数尝试求出结果。我们把求质数的范围作为一个参数，如果十万范围里面求不出结果，我们可以扩大筛选范围。6541367***最后三位数未知。但是我们可以知道：
最小值：6541367000
最大值：6541367999
遍历筛选的质数集合，满足三个条件：
(a)、同时用最大值和最小值分别除以集合中遍历的元素，所得两个商为一个浮点数，浮点数落在连续的两个整数范围内。因为质数为奇数，所以我们取这两个整数中的奇数。取整的两个奇数判等。
(b)、判等的奇数，也必在筛选的质数集合中。
(c)、判等的奇数和遍历的质数之积，减去与1000求余所得结果为最小值。
Talk is cheap.Show me your code.多说无用，看我行动。
1 import Foundation
2 class Solution {
3 func findBeauty2(_ number:Int, _ target: Int) -> [Int] {
4 var primes = Set(2...number)
5 //埃拉托色尼筛选法
6 (2...Int(sqrt(Double(number)))).forEach {
7 let _ = primes.subtract(stride(from: 2*$0, through: number, by: $0))
8 }
9 let nums:[Int] = Array(primes).sorted()
10 //最小值
11 let minNum:Int = target * 1000
12 //最大值
13 let maxNum:Int = minNum + 999
14 //遍历数组
15 for i in 0..<nums.count - 1
16 {
17 let num1:Int = getOdd(maxNum,nums[i])
18 let num2:Int = getOdd(minNum,nums[i])
19 let num3:Int = num1 * nums[i]
20 //质数必须是奇数
21 if num1 == num2 && nums.contains(num1) && minNum == (num3 - num3 % 1000)
22 {
23 print(num3)
24 return([nums[i],num1])
25 }
26 }
27 return [-1,-1]
28 }
29
30 //质数必为奇数，获取奇数
31 func getOdd(_ num1:Int,_ num2:Int) -> Int
32 {
33 let number:Int = Int(ceil(Double(num1) / Double(num2)))
34 return number % 2 == 0 ? (number - 1) : number
35 }
36 }
点击：Playground测试
1 //测试
2 print(Solution().findBeauty2(100000, 6541367))
3 //Print 6541367489
4 //Print [67049, 97561]
但是我们还没拿到美人的微信大号呢！经过我夜观天象，掐指一算。获得美女学霸其人真正微信：(点击左上角菜单，扫一扫加博主微信。向博主咨询)
请发表评论