Fork me on GitHub

只想找IT男結婚的清華小姐姐,居然出了這么一道難題?

最近有一張奇特的征婚廣告出現在了各個互聯網人的微信群中,大概意思是一個清華畢業的北京小姐姐征婚,只想找IT男,要求是智商要高。題目如下:

土生土長的北京妞兒,在胡同里長大,房不多,就一個四合院和近郊的別墅。不算美如天仙但還算標致,在清華讀的經管,現在在做基金經理(不想被人肉,就不暴露單位啦),個人擅長基本面分析,價值投資。現在只想找個聰明靠譜的IT男。硬性要求是年齡,不要超過88年,還有不要特別矮或胖。 我對智商的要求比較高,下面就出個題測試下。我的微信ID是大寫字母NY后面跟著兩個質數,大的在前,小的在后,乘積是707829217,可直接搜索添加,另外還有個附加題目,在剛剛微信ID的數字中,從1開始到這個數字的奇數序列里,一共出現了多少個3,如果私信我正確的答案,我將直接邀你見面!期待緣分降臨~

問題

  • 從這個題目中我們可以得到兩個重要信息,小姐姐的微信號格式為:NY(大質數)(小質數),我們設大質數為i,小質數為j,i*j的乘積為707829217,然后求出i跟j的值就得到了小姐姐的微信號了。

  • 題目中還有一個附加題目,求從1開始到i*j乘積的奇數數列中,一共出現了多少個3?

解題思路

前一個問題主要是讓我們尋找兩個質數,且乘積等于給定的數,我們先來回顧下數學知識,什么是質數?

質數定義:質數(Prime number),又稱素數,指在大于1的自然數中,除了1和該數自身外,無法被其他自然數整除的數(也可定義為只有1與該數本身兩個正因數的數)。大于1的自然數若不是素數,則稱之為合數(也稱為合成數)。例如,5是個素數,因為其正約數只有1與5。而6則是個合數,因為除了1與6外,2與3也是其正約數。算術基本定理確立了素數于數論里的核心地位:任何大于1的整數均可被表示成一串唯一素數之乘積。為了確保該定理的唯一性,1被定義為不是素數,因為在因式分解中可以有任意多個1(如3、1×3、1×1×3等都是3的有效約數分解)。——來自維基百科

了解了質數的定義之后,我嘗試用python來尋找從0到10的質數,我們可以知道10以內的質數為2,3,5,7,代碼如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
# 構造一個range,從2開始循環到10
for n in range(2, 11):
# 2是素數,如果n等于2,將2打印出來
if n == 2:
print(n)
continue
# 構造一個從2到n的range
for i in range(2, n):
# 如果n能否整除i,能則說明當前數n不為素數
if (n % i) == 0:
break
else:
print(n)

通過運行以上代碼我們成功的得到了10以內的素數,得到了素數之后我們將得到的值添加到一個列表List,然后循環兩次列表,讓列表中的數兩兩相乘取乘積,當乘積等于給定值707829217的時候,我們就將兩個素數打印出來。

那這個時候有個小問題來了,給定值的大小為億,我們大膽的猜測下這兩個數應該會小于10萬,因為大于10萬的兩個數相乘會到百億級別,所以應該是兩個小于10萬的數。ok,到這里就簡單了,我們只要找出10萬以內的素數即可,當然這里有兩個辦法,第一是用上面代碼找出10萬以內所有素數,也可以直接到網上下載10萬以內所有的素數,然后下載下來循環相乘即可。我嘗試了以下代碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 設定一個空列表,用于插入數據
sushu = []
for n in range(2, 100000):
if n == 2:
print(n)
continue
for i in range(2, n):
if (n % i) == 0:
break
else:
print(n)
sushu.append(n)

for i in sushu:
for j in sushu:
k = i*j
if k == 707829217:
print("找到啦!")
print(f"i:{i}")
print(f"j:{j}")

然后運行以上代碼,大概2到3分鐘就找到了,i的值為:86627,j的值為8171,所以小姐姐的微信號就是NY866278171,通過測試我們也成功的搜索出來了小姐姐的微信號。

EZoHaj.png

然后小姐姐還有一個問題,就是從1開始到866278171的奇數序列中一共出現了多少次3?我的解決辦法是,將這個列表中所有的奇數序列轉換成為列表,然后再轉化成為字符串,最好統計這個字符串中一共出現了多少次3(手動捂臉),這個方法雖然笨,但是還是可以實現的,代碼如下:

1
2
3
4
5
6
7
8
list1 = []
for i in range(1, 866278171,2):
list1.append(i)

# 將列表轉化成為字符串
str1 = "".join(map(str, list1))
# 統計字符串中某個數出現的次數
print(f"3出現的次數為{str1.count('3')}")

理論上運行上述代碼就能得到結果了,但實際有個很坑爹的問題,就是因為這個數太大了,需要循環很久,我一開始執行這段代碼的時候發現電腦內存飆升,而且半天都計算不出結果。一度我以為這是哪個傻缺故意搞出來坑人的題,后來想想這個方法性能的確太慢了,但總算能夠算出結果,等于:441684627。所以我后續需要想辦法改進了下這個算法。

最后,附上小姐姐的背影圖。

EmSmr9.md.jpg

參考資料

[算法]兩個質數的乘積是707829217,求解該質數

贵州体育彩票11选5