Project Euler 046~050
关于啥是Project Euler 详见 https://projecteuler.net/about
观前声明：
这是个人兴趣使然的对自己入坑pe的记录，仅提供思路和部分代码；各个方面肯定都是有着优化与提升空间的，甚至在许多大佬看来这应该是初学者的浅薄而未经剪枝的丑码，如果能帮到有兴趣的人自是最好，也欢迎能醍醐灌顶的深度讨论。
大佬看到了笑笑就行，还请轻喷。
带着恶意，抬杠者...俺也喷不过您，也不能拿您咋样...毕竟这只是我个人兴趣使然的行为或者说是学习记录分享。 （说是记录，但因为是早先写的所以其实是在各种意义上公开处刑和吐槽自己 并尝试补救优化）
语言是c++，用的VS平台
前排提示：本期是质数与数组数互化.
Goldbach's other conjecture
Problem 46
It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.
9 = 7 + 2×1^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2
It turns out that the conjecture was false.
What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
除了著名的哥德巴赫猜想，这个人还提出了另一个猜想：每个奇合数能分成一个质数与一个平方数乘2的和；比如9=7+2×1^2，15=7+2×2^2...
但这个猜想被证明是错的，找到不能满足这一性质的最小的奇合数，即第一个反例。
有意思，变相的让我们来证否猜想了。思路也很简单，先跑一个质数表，对每个奇合数，检验每个小于它的质数能不能完成这一性质的分解，如果不存在分解，就说明找到了。
质数表筛子跑一遍，但这里为了方便我们可以直接存储质数，比如prime[n]代表第n个质数，这样在之后的检验里会少跑一点，实现方法用之前的题的思路稍稍改一下不难。再不济每个n用定义逐个检验因子也行，反正规模不大;姑且放个按定义拉跨的实现：
int getprime(void)
{
int n = 3, i, count = 1;
prime[1] = 2;
while (n <= 1000000)
{
int check = 1;
for (i = 2; i * i <= n; i++)
if (!(n % i)) { check = 0; break; }
if (check) prime[++count] = n;
n += 2;
}
return count;
}
验证平方数也很简单，开跟后看看是否为整数即可。double np=sqrt(n) 如果(int)np==np就行了；或者用一个不容易让系统犯病的检验：int np=sqrt(n)+eps eps为0.0000001 （因为double型的整数有时会以a.999999..来表示a+1）然后如果np*np==n就说明是整数。
对每个奇合数用一个while循环跑遍所有小于它的质数：
主函数向上暴搜n即可。
ans：5777
第47题：
Distinct primes factors
Problem 47
The first two consecutive numbers to have two distinct prime factors are:
14 = 2 × 7
15 = 3 × 5
The first three consecutive numbers to have three distinct prime factors are:
644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.
Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?
第一个都为2个质因子乘积得到的连续的2个数是14和15：
14 = 2 × 7
15 = 3 × 5
第一个都为3个质因子乘积得到的连续的3个数是644 645 646：
644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.
（注意2只算1个质数）
找到第一个都为4个质因子乘积得到的连续的4个数，获得的这连续的四个数字的第一个数作为答案。
这题依旧懒得思考的直接选择了暴搜，没啥实用价值.但对这题有效。判断函数：检验n是否能分解为4个质数的乘积，事实上由后验的不严谨考量，这个检验不必一定要判断出n的4个质数分解，连续的4个数都拥有4个不同的质因子的概率与连续的4个数都能被4个不同的质数分解的概率在较小的数字区间分布中是几乎相等的。所以可以采用一种偷懒的写法：
如果n~n+3都有4个质因子那么checknfour(n)会返回n。
主函数中遍历得到第一个这样的n。
这样的写法说好听点算因运气过了，难听点就是不算真正解出来. 但从结果来看，还挺快
ans：134043
第48题：
Self powers
Problem 48
The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317.
Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000.
算出^1 + 2^2 + 3^3 + ... + 1000^1000.的最后10位数。
之前算大数的题都用的数组模拟，但这次终于可以不用了，注意“最后10位数”，所以每次算完取模，余10000000000即可，这样就算是拉跨的c++也不会因为溢出而崩掉了
（今天隔壁视频up主市博司刚跟俺说MMA(mathematica)能够无上限处理大数（只要内存够），着实酸。他也在用MMA做pe，对MMA感兴趣或想看看别的语言怎么解决pe问题的不妨去学习下）
取模写起来还是很随意的。
ans：9110846700
第49题：
Prime permutations
Problem 49
The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.
There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.
What 12-digit number do you form by concatenating the three terms in this sequence?
1487，4817，8147，这一组数公差为3330，并且每个数都是质数，且4817为1487之后的字典排序，8147为4817之后的字典排序。在1位，2位，3位数中莫得这样性质的序列，但是4位数中还存在这种性质的递增序列，找到它们，按顺序拼合为12位数作为答案。
简而言之，思路的方向有多种，我们可以先获得所有4位数的质数，并用一个二维数组储存每个4位数质数的每位数，方便后续处理A[9001][4]（数组化数，怎么跑质数，怎么实现存储都不讲了，要么讲过要么太简单）；
（然后我的思路开始拉跨了）
对于储存在A中的3序号n1,n2,n3(对应A[n1][],A[n2][],A[n3][])
先把它们化成数，检验是否为等差序列；再检验是否全排列数字相同（可以用sort排序后再判断每个对应数字是否相等）相等说明找到了（由储存规则，如果n1<n2<n3对应的3个质数也是有着相同的大小关系）
主函数中对每个(n1,n2,n3)对用3个for暴搜检验即可
之所以说拉跨是因为这个思路写出来的代码需要跑个10s左右 相当慢了，是前50题中几道不能秒出的之一。
答案是2969 6299 9629 公差为3330的质数字典排序等差序列（欸怎么一样.性质里说的是公差恒为这个值吗岂可修...）
ans：296962999629
第50题：
Consecutive prime sum
Problem 50
The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?
41能被连续的质数相加得到，41 = 2 + 3 + 5 + 7 + 11 + 13，并且41是100以内能分解出最长的质数链的数；1000以内的能分解出最长质数链的质数为953；那么1000000以内呢？
这题比起前面几道就很随意了，用46题的那种质数表，prime[n]代表第n个质数。检验一个数n的链长：从第i个质数开始往上加一直加到与n相等或溢出，溢出说明从第i个质数开始不能生成连续的质数链，那么再从i+1开始检验（i从1开始）；返回最大的链长，都没有则返回0：
主函数逐个检验1000000内的没个质数即可。（思路简单，但也是不能秒出的，估计跟质数表的得到写法有关）
ans：997651
好的.那么前50题就圆满完结了。其实pe给每道题都评了个难度等级，按百分比算，比例越高越难，1~50的难道评级都是相等，均为5%。
也就是说，官方是认为前50道均为水题的，50题之后才开始出现5%以上难度的题。
50题之后可能不会5题5题更了.一方面可以多水点，另一方面一次性5题当天思考+消化有点些许强人所难 不过前50题官方认定的水题就无所谓了。
那么有缘再见.
