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,求解该质数