關(guān)于啥是Project Euler 詳見 https://projecteuler.net/about?

觀前聲明：?

1. 這是個人興趣使然的對自己入坑pe的記錄，僅提供思路和部分代碼；各個方面肯定都是有著優(yōu)化與提升空間的，甚至在許多大佬看來這應(yīng)該是初學者的淺薄而未經(jīng)剪枝的丑碼，如果能幫到有興趣的人自是最好，也歡迎能醍醐灌頂?shù)纳疃扔懻摗??

2. 大佬看到了笑笑就行，還請輕噴。

3. 帶著惡意，抬杠者...俺也噴不過您，也不能拿您咋樣...畢竟這只是我個人興趣使然的行為或者說是學習記錄分享。?（說是記錄，但因為是早先寫的所以其實是在各種意義上公開處刑和吐槽自己 并嘗試補救優(yōu)化）

4. 語言是c++，用的VS平臺

前排提示：本期是質(zhì)數(shù)與數(shù)組數(shù)互化.

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?

除了著名的哥德巴赫猜想，這個人還提出了另一個猜想：每個奇合數(shù)能分成一個質(zhì)數(shù)與一個平方數(shù)乘2的和；比如9=7+2×1^2，15=7+2×2^2...

但這個猜想被證明是錯的，找到不能滿足這一性質(zhì)的最小的奇合數(shù)，即第一個反例。

有意思，變相的讓我們來證否猜想了。思路也很簡單，先跑一個質(zhì)數(shù)表，對每個奇合數(shù)，檢驗每個小于它的質(zhì)數(shù)能不能完成這一性質(zhì)的分解，如果不存在分解，就說明找到了。

質(zhì)數(shù)表篩子跑一遍，但這里為了方便我們可以直接存儲質(zhì)數(shù)，比如prime[n]代表第n個質(zhì)數(shù)，這樣在之后的檢驗里會少跑一點，實現(xiàn)方法用之前的題的思路稍稍改一下不難。再不濟每個n用定義逐個檢驗因子也行，反正規(guī)模不大;姑且放個按定義拉跨的實現(xià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;

}

驗證平方數(shù)也很簡單，開跟后看看是否為整數(shù)即可。double np=sqrt(n)? 如果(int)np==np就行了；或者用一個不容易讓系統(tǒng)犯病的檢驗：int np=sqrt(n)+eps? eps為0.0000001 （因為double型的整數(shù)有時會以a.999999..來表示a+1）然后如果np*np==n就說明是整數(shù)。

對每個奇合數(shù)用一個while循環(huán)跑遍所有小于它的質(zhì)數(shù)：

主函數(shù)向上暴搜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 = 22 × 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個質(zhì)因子乘積得到的連續(xù)的2個數(shù)是14和15：

14 = 2 × 7
15 = 3 × 5

第一個都為3個質(zhì)因子乘積得到的連續(xù)的3個數(shù)是644 645 646：

644 = 22 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

（注意2只算1個質(zhì)數(shù)）

找到第一個都為4個質(zhì)因子乘積得到的連續(xù)的4個數(shù)，獲得的這連續(xù)的四個數(shù)字的第一個數(shù)作為答案。

這題依舊懶得思考的直接選擇了暴搜，沒啥實用價值.但對這題有效。判斷函數(shù)：檢驗n是否能分解為4個質(zhì)數(shù)的乘積，事實上由后驗的不嚴謹考量，這個檢驗不必一定要判斷出n的4個質(zhì)數(shù)分解，連續(xù)的4個數(shù)都擁有4個不同的質(zhì)因子的概率與連續(xù)的4個數(shù)都能被4個不同的質(zhì)數(shù)分解的概率在較小的數(shù)字區(qū)間分布中是幾乎相等的。所以可以采用一種偷懶的寫法：

如果n~n+3都有4個質(zhì)因子那么checknfour(n)會返回n。

主函數(shù)中遍歷得到第一個這樣的n。

這樣的寫法說好聽點算因運氣過了，難聽點就是不算真正解出來. 但從結(jié)果來看，還挺快

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位數(shù)。

之前算大數(shù)的題都用的數(shù)組模擬，但這次終于可以不用了，注意“最后10位數(shù)”，所以每次算完取模，余10000000000即可，這樣就算是拉跨的c++也不會因為溢出而崩掉了

（今天隔壁視頻up主市博司剛跟俺說MMA(mathematica)能夠無上限處理大數(shù)（只要內(nèi)存夠），著實酸。他也在用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，這一組數(shù)公差為3330，并且每個數(shù)都是質(zhì)數(shù)，且4817為1487之后的字典排序，8147為4817之后的字典排序。在1位，2位，3位數(shù)中莫得這樣性質(zhì)的序列，但是4位數(shù)中還存在這種性質(zhì)的遞增序列，找到它們，按順序拼合為12位數(shù)作為答案。

簡而言之，思路的方向有多種，我們可以先獲得所有4位數(shù)的質(zhì)數(shù)，并用一個二維數(shù)組儲存每個4位數(shù)質(zhì)數(shù)的每位數(shù)，方便后續(xù)處理A[9001][4]（數(shù)組化數(shù)，怎么跑質(zhì)數(shù)，怎么實現(xiàn)存儲都不講了，要么講過要么太簡單）；

（然后我的思路開始拉跨了）

對于儲存在A中的3序號n1,n2,n3(對應(yīng)A[n1][],A[n2][],A[n3][])

先把它們化成數(shù)，檢驗是否為等差序列；再檢驗是否全排列數(shù)字相同（可以用sort排序后再判斷每個對應(yīng)數(shù)字是否相等）相等說明找到了（由儲存規(guī)則，如果n1<n2<n3對應(yīng)的3個質(zhì)數(shù)也是有著相同的大小關(guān)系）

主函數(shù)中對每個(n1,n2,n3)對用3個for暴搜檢驗即可

之所以說拉跨是因為這個思路寫出來的代碼需要跑個10s左右 相當慢了，是前50題中幾道不能秒出的之一。

答案是2969? 6299 9629 公差為3330的質(zhì)數(shù)字典排序等差序列（欸怎么一樣.性質(zhì)里說的是公差恒為這個值嗎豈可修...）

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能被連續(xù)的質(zhì)數(shù)相加得到，41 = 2 + 3 + 5 + 7 + 11 + 13，并且41是100以內(nèi)能分解出最長的質(zhì)數(shù)鏈的數(shù)；1000以內(nèi)的能分解出最長質(zhì)數(shù)鏈的質(zhì)數(shù)為953；那么1000000以內(nèi)呢？

這題比起前面幾道就很隨意了，用46題的那種質(zhì)數(shù)表，prime[n]代表第n個質(zhì)數(shù)。檢驗一個數(shù)n的鏈長：從第i個質(zhì)數(shù)開始往上加一直加到與n相等或溢出，溢出說明從第i個質(zhì)數(shù)開始不能生成連續(xù)的質(zhì)數(shù)鏈，那么再從i+1開始檢驗（i從1開始）；返回最大的鏈長，都沒有則返回0：

主函數(shù)逐個檢驗1000000內(nèi)的沒個質(zhì)數(shù)即可。（思路簡單，但也是不能秒出的，估計跟質(zhì)數(shù)表的得到寫法有關(guān)）

ans：997651

好的.那么前50題就圓滿完結(jié)了。其實pe給每道題都評了個難度等級，按百分比算，比例越高越難，1~50的難道評級都是相等，均為5%。

也就是說，官方是認為前50道均為水題的，50題之后才開始出現(xiàn)5%以上難度的題。

50題之后可能不會5題5題更了.一方面可以多水點，另一方面一次性5題當天思考+消化有點些許強人所難 不過前50題官方認定的水題就無所謂了。

那么有緣再見.