【算法】这么容易就得到小姐姐的微信

一、背景

群里一个同事发了一个照片，一看是一个小姐姐，而且图片的信息量比较多。

土生土长的北京妞儿，在胡同里长大，房不多，就一个四合院和近郊的别墅。不算美如天仙但还算标致，在清华读的经管，现在在做基金经理(不想被人肉，就不暴露单位啦)，个人擅长基本面分析，价值投资。现在只想找个聪明靠谱的IT男。硬性要求是年龄，不要超过88年，还有不要特别矮或胖。  


我对智商的要求比较高，下面就出个题测试下。我的微信ID是大写字母NY后面跟着两个质数，大的在前，小的在后，乘积是707829217，可直接搜索添加，另外还有个附加题目，在刚刚微信ID的数字中，从1开始到这个数字的奇数序列里，一共出现了多少个3，如果私信我正确的答案，我将直接邀你见面!期待缘分降临~   

分析一下，关键信息有这些。

个人信息：北京人，有一个四合院和近郊别墅，毕业于清华经济管理专业，目前职业基金经理（价值投资）。
基本要求：IT男，年龄不超过88年，身高不要太矮，体重不要太胖（后两个条件好模糊）。
智商考验：数字707829217质数分解，然后计算出微信号。
智商加分题：找出1到微信号的奇数序列中，出现3的次数。

考虑到这个同事目前单身，可能看上这个小姐姐了。
看来我有必要帮忙帮忙，算出这些智商考研题。
考虑到小姐姐到时候可能会问他怎么算的，这里还要写个讲解，不然到时候就露馅了。

好了，下面我们来看看智商考研题和加分题怎么做吧。

一、质数分解

由于已经确定707829217是两个质数之积，所以我们只需要求出其中一个，另一个一除就出来了。
而较小的质数肯定小于等于srqt(707829217)，即小于等于这个数字开方后的数字。
那你只需要使用基本的筛法，筛出srqt(707829217)内的所有质数。大概是3万以内的质数吧，大概估计一下有几千个素数。

质数表求出来后，我们枚举所有质数，判断这个质数是否可以被707829217整除，如果可以，就找到了。

代码大概如下，确实计算出来了一对质数。

二、3的个数

这道题抽象一下，就是求小于等于N的奇数序列内，3的个数有多少个？

如果你之前用心的看我的文章的话，会发现这类题之前已经给你们讲解过至少四五次了。

这类题有一个通用的解法。

假设输入的数字是abcdef,我们可以将答案分为两类数据。

1.full_lt(a)，含义为最高位为0~a-1时，低位可以是任意值的，此时有多个答案。
2.eq_lt(a, bcdef)，含义为最高位为a时，低位是有限制的，需要不大于输入的数，此时有多少个答案。

所以我们可以写出一个通用的公式find() = full_lt() + eq_lt()。

对于full_lt一般是一个固定的公式，可以计算出答案来。
对于eq_lt，则可以转化为一个与find有关的公式。
这样递归下去，即可计算出答案。

具体到这道题，是求奇数序列里面3的个数。

假设输入的数据是5647391。

full_lt(5)则需要拆分为两部分：3为前缀时答案的个数与3不是前缀的答案。
3为前缀时，所有序列的最高位都有一个3，这个有奇数序列个（full(len)=10^len/2）。
3为前缀时，非最高位3的个数就和3不是前缀的答案一样了，假设为fullbit。
所以公式可以写为full_lt()=full() + 5 * fullbit()

对于fullbit()含义为0001~9999内，3的个数。
这个从个位递推，很容易计算出来。
公式大概是fullbit(len)=full(len-1)+10*fullbit(len-1)
几何意义是与full_lt完全一样，不过这里是完整的10个数字。
这里我们暂且就不合并了。

而对于eq_lt也分两部分。
一部分是只统计最高位，有多少个3（只有最高位恰好是3是生效），一个是递归下去有多少个。
还是上面的例子，在倒数第二位时，遇到了3。
所以对于300~391内奇数序列个数都会累加一次3，个数大概是(91+1)/2。

好吧，强行看到这里的人我知道你们看晕了。
这个可以看下下面的公示图，应该清晰点。

四、最后

至于这两个智商题的答案，我就不提供了。
至于这两个源代码，公众号后台回复小姐姐微信获取。

对了，为了核对你的答案是否正确，我可以说出3个数的最后四位，是4627。

PS：这道题已经给你们讲解了，代码也给你们了，小姐姐能不能拿到手就看你们自己了。

-EOF-