首页 > 代码库 > Project-Euler problem 1-50
Project-Euler problem 1-50
最近闲的做了下Project Euler 上的题目，前面50题都比较简单，简单总结下。代码一般是Python和C/C++的 用Python 做这些题目简直是酸爽啊
一下代码可能不一定是我的，因为不知道论坛里面的回复不是永久的，所以我的代码有的丢了，可能找个和我的意思相近的代码。题目翻译是从
欧拉计划 | Project Euler 中文翻译站上面Copy 的表告我。
Problem 1 Multiples of 3 and 5
10以下的自然数中，属于3和5的倍数的有3,5,6和9，它们之和是23.找出1000以下的自然数中，属于3和5的倍数的数字之和。
print sum([x for x in range(1000) if x%3==0 or x%5==0])
Problem 2 Even Fibonacci numbers
斐波那契数列中的每一项被定义为前两项之和。从1和2开始，斐波那契数列的前十项为：
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
考虑斐波那契数列中数值不超过4百万的项，找出这些项中值为偶数的项之和。
ls=[1,1] ans=0 while ls[-1] <4000000: ls.append(ls[-1]+ls[-2]) if (ls[-1]&1) == 0: ans+=ls[-1] python make it easy
3 Largest prime factor
13195的质数因子有5,7,13和29.600851475143的最大质数因子是多少？
>>> ans=0 >>> i=3 >>> num=600851475143 >>> while i<= num: if num%i==0: num/=i ans=i i-=1 i+=1 >>> ans 68574 Largest palindrome product
一个回文数指的是从左向右和从右向左读都一样的数字。最大的由两个两位数乘积构成的回文数是9009 = 91 * 99.找出最大的有由个三位数乘积构成的回文数。
>>>def isPal(n): m=n r=0; while m <> 0: r=r*10+m%10 m/=10 return n==r >>> ans=0 >>> for i in range(100,999,1): for j in range (i,999,1): if isPal(i*j) and i*j >ans: ans=i*j >>> ans 9066095 Smallest multiple
2520是最小的能被1-10中每个数字整除的正整数。最小的能被1-20中每个数整除的正整数是多少？
>>>def gcd (a ,b):
if a<b:
a,b=b,a
if b==0:
return a
else:
return gcd(b,a%b)
>>>for i in range(1,21,1):
tmp=gcd(i,ans)
ans=ans*i/tmp
>>>ans
232792560L6 Sum square difference前十个自然数的平方和是：
1^2 + 2^2 + ... + 10^2 = 385
前十个自然数的和的平方是：
(1 + 2 + ... + 10)^2 = 55^2 = 3025
所以平方和与和的平方的差是3025 ? 385 = 2640.
找出前一百个自然数的平方和与和平方的差。
sum(range(1,101,1))**2-sum([x*x for x in range(1,101,1)])7 10001st prime
前六个质数是2,3,5,7,11和13，其中第6个是13.第10001个质数是多少？
>>>j=3 >>> prime=[2] >>> while i<10001: tmp=j for x in prime: if tmp%x==0: tmp=0 break if tmp<>0: prime.append(j) i+=1 j+=1 >>> prime[10000] 1047438 Largest product in a series
找出以下这个1000位的整数中连续13个数字的最大乘积。 数太占面积不贴了
暴力吧，代码丢了
9 Special Pythagorean triplet
一个毕达哥拉斯三元组是一个包含三个自然数的集合，a<b<c，满足条件：
a^2 + b^2 = c^2
例如：3^2 + 4^2 = 9 + 16 = 25 = 5^2.
已知存在并且只存在一个毕达哥拉斯三元组满足条件a + b + c = 1000。
找出该三元组中abc的乘积，代码丢了，论坛偷的代码
def main():
for m in range(2, 500):
for n in range(1, m):
if 2*m*n + 2*m*m == 1000:
a, b, c = 2*m*n, m*m - n*n, m*m + n*n
print(a, b, c)
print(a*b*c)
return
if __name__ == "__main__":
main()10 Summation of primes
10以下的质数的和是2 + 3 + 5 + 7 = 17.找出两百万以下所有质数的和。筛法随便搞下就可以
#include<iostream>
#define MAXN 2000001
using namespace std;
int bprime[MAXN]={0};
int main()
{
for (int i=2;i<2000;i++)
if(!bprime[i])
for(int j=2;i*j<=MAXN;j++)
bprime[i*j]=1;
long long ans=0;
for(int i=2;i<MAXN;i++)
if(!bprime[i]) ans+=i;
cout<<ans<<endl;
return 0;
}11 Largest product in a grid在以下这个20×20的网格中，四个处于同一对角线上的相邻数字用红色标了出来：
大数字矩阵不贴了
这四个数字的乘积是：26 × 63 × 78 × 14 = 1788696.
在这个20×20网格中，处于任何方向上（上，下，左，右或者对角线）的四个相邻数字的乘积的最大值是多少？
#include<iostream>
#include<algorithm>
using namespace std;
int data[30][30]={0};
int main()
{
for(int i=0;i<20;i++)
for(int j=0;j<20;j++)
cin>>data[i+5][j+5];
int ans=0,tmp;
for(int i=5;i<25;i++)
for(int j=5;j<25;j++)
{
tmp=data[i][j]*data[i+1][j]*data[i+2][j]*data[i+3][j];
ans=max(tmp,ans);
tmp=data[i][j]*data[i+1][j+1]*data[i+2][j+2]*data[i+3][j+3];
ans=max(tmp,ans);
tmp=data[i][j]*data[i][j+1]*data[i][j+2]*data[i][j+3];
ans=max(tmp,ans);
tmp=data[i][j]*data[i-1][j+1]*data[i-2][j+2]*data[i+1][j-1];
ans=max(tmp,ans);
}
cout<<ans<<endl;
return 0;
}12 Highly divisible triangular number三角形数序列是由对自然数的连加构造而成的。所以第七个三角形数是1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. 那么三角形数序列中的前十个是：
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
下面我们列出前七个三角形数的约数：
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
可以看出28是第一个拥有超过5个约数的三角形数。
那么第一个拥有超过500个约数的三角形数是多少？
#include<iostream>
using namespace std;
int getFactors(long long n)
{
int ans=0;
for(int i=1;i*i<=n;i++)
if(n%i==0)
ans+=2;
return ans;
}
int main()
{
long long sum=1;
int i=1;
while(getFactors(sum)<500)
sum+=++i;
cout<<sum<<" "<<i<<" "<<getFactors(sum)<<endl;
return 0;
}13 Large sum找出以下100个50位数之和的前十位数字。数字不贴了，Python支持大数这就不是问题了
14 Longest Collatz sequence
以下迭代序列定义在整数集合上：
n → n/2 (当n是偶数时)
n → 3n + 1 (当n是奇数时)
应用以上规则，并且以数字13开始，我们得到以下序列：
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
可以看出这个以13开始以1结束的序列包含10个项。虽然还没有被证明（Collatz问题），但是人们认为在这个规则下，以任何数字开始都会以1结束。
以哪个不超过100万的数字开始，能给得到最长的序列？
注意: 一旦序列开始之后，也就是从第二项开始，项是可以超过100万的。
def get(n): while n<>1: if n&1: n=3*n+1 else: n>>=1 yield n >>> ans=[0,0] >>> for x in xrange(1,1000001,1): tmp=len([i for i in get(x)]) if tmp>ans[0]: ans[0]=tmp ans[1]=x >>> ans [524, 837799]15 Lattice paths
从一个2
2网格的左上角开始，有6条（不允许往回走）通往右下角的路。
对于2020的网格，这样的路有多少条？
16 Power digit sum
2^15 = 32768 并且其各位之和为 is 3 + 2 + 7 + 6 + 8 = 26.
2^1000 的各位数之和是多少？
print sum([int(x) for x in str(2**1000)])
17 Number letter counts
如果用英文写出数字1到5: one, two, three, four, five, 那么一共需要3 + 3 + 5 + 4 + 4 = 19个字母。
如果数字1到1000（包含1000）用英文写出，那么一共需要多少个字母？
注意: 空格和连字符不算在内。例如，342 (three hundred and forty-two)包含23个字母； 115 (one hundred and fifteen)包含20个字母。"and" 的使用与英国标准一致。
比较麻烦，我搜了一下
18 Maximum path sum I
从下面的三角形的顶端开始，向下面一行的相邻数字移动，从顶端到底端的最大总和为23.
3
7 4
2 4 6
8 5 9 3
也就是 3 + 7 + 4 + 9 = 23.
找出从以下三角形的顶端走到底端的最大总和：
简单的动态规划
#include<iostream>
using namespace std;
int data[20][20];
int main()
{
for(int i=0;i<15;i++)
for(int j=0;j<=i;j++)
cin>>data[i][j];
for(int i=13;i>=0;i--)
for(int j=0;j<=i;j++)
data[i][j]+=max(data[i+1][j],data[i+1][j+1]);
cout<<data[0][0]<<endl;
return 0;
}19 Counting Sundays
以下是一些已知信息，但是或许你需要自己做一些其他的调查。
1900年1月1日是星期一。
30天的月份有：9月，4月，6月，11月。
此外的月份都是31天，当然2月除外。
2月在闰年有29天，其他时候有28天。
年份可以被4整除的时候是闰年，但是不能被400整除的世纪年（100的整数倍年）除外。
20世纪（1901年1月1日到2000年12月31日）一共有多少个星期日落在了当月的第一天？论坛的代码
from datetime import date print(sum([1 for year in range(1901,2001) for mouth in range(1,13) if date(year,mouth,1).weekday() == 6]))20 Factorial digit sum
n! = n × (n ? 1) × ... × 3 × 2 × 1
例如， 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,
那么10!的各位之和就是3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.
算出100!的各位之和。
>>> def fac(n): ans=1 for i in range(1,n+1,1): ans*=i return ans >>> sum([int(x) for x in [y for y in str(fac(100))]]) 64821 Amicable numbers
d(n)定义为n 的所有真因子（小于 n 且能整除 n 的整数）之和。
如果 d(a) = b 并且 d(b) = a, 且 a ≠ b, 那么 a 和 b 就是一对相亲数（amicable pair），并且 a 和 b 都叫做亲和数（amicable number）。
例如220的真因子是 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 和 110; 因此 d(220) = 284. 284的真因子是1, 2, 4, 71 和142; 所以d(284) = 220.
计算10000以下所有亲和数之和。
>>> def d(n): ans=1 tmp=2 while tmp*tmp<n: if n%tmp==0: ans+=tmp ans+=n/tmp tmp+=1 if tmp*tmp==n: ans+=tmp return ans >>> ans=0 >>> for x in xrange(1,10000,1): if x==d(d(x)) and x!=d(x): ans+=x >>> ans 3162622 Names scores
文件names.txt （右键另存为）是一个46K大小的文本文件，包含5000多个英文名字。利用这个文件，首先将文件中的名字按照字母排序，然后计算每个名字的字母值，最后将字母值与这个名字在名字列表中的位置相乘，得到这个名字的得分。
例如将名字列表按照字母排序后， COLIN这个名字是列表中的第938个，它的字母值是3 + 15 + 12 + 9 + 14 = 53。所以COLIN这个名字的得分就是938 × 53 = 49714.
文件中所有名字的得分总和是多少？
>>>name=['' .....]
>>>name.sort()
>>> def cal(s):
ans=0
for i in s:
ans+=ord(i)-ord('A')+1
return ans
>>> for i in xrange(len(name)):
ans+=(i+1)*cal(name[i])
>>>ans23 Non-abundant sums
如果一个数的所有真因子之和等于这个数，那么这个数被称为完全数。例如，28的所有真因子之和为1 + 2 + 4 + 7 + 14 = 28，所以28是一个完全数。
如果一个数的所有真因子之和小于这个数，称其为不足数，如果大于这个数，称其为过剩数。
12是最小的过剩数，1 + 2 + 3 + 4 + 6 = 16。因此最小的能够写成两个过剩数之和的数字是24。经过分析，可以证明所有大于28123的数字都可以被写成两个过剩数之和。但是这个上界并不能被进一步缩小，即使我们知道最大的不能表示为两个过剩数之和的数字要比这个上界小。
找出所有不能表示为两个过剩数之和的正整数之和。
#include<iostream>
using namespace std;
const int cnt=28124;
bool is[cnt]={0};
int abundant[cnt];
int num=0;
bool isAbundant(int n)
{
int sum=1,i;
for (i=2;i*i<n;i++)
if(n%i==0)
sum+=(i+n/i);
if(i*i==n)
sum+=i;
return sum>n;
}
int main()
{
for(int i=1;i<cnt;i++)
if(isAbundant(i))
abundant[num++]=i;
for(int i=0;i<num;i++)
for(int j=i;j<num;j++)
if(abundant[i]+abundant[j]<cnt)
is[abundant[i]+abundant[j]]=true;
int ans=0;
for(int i=1;i<cnt;i++)
if(!is[i])
ans+=i;
cout<<ans<<endl;
return 0;
}24 Lexicographic permutations排列是一个物体的有序安排。例如3124是1,2,3,4的一种排列。如果所有的排列按照数值或者字母序排序，我们称其为一个字典序。0,1,2的字典排列有：
012 021 102 120 201 210
0, 1, 2, 3, 4, 5, 6, 7, 8，9的第100万个字典排列是什么？
STL is useful
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int data[]={0,1,2,3,4,5,6,7,8,9};
for(int i=1;i<1000000;i++)
next_permutation(data,data+10);
for(int j=0;j<10;j++)
cout<<data[j];
return 0;
}25 1000-digit Fibonacci number以下是斐波那契数列的递归定义：
Fn = Fn?1 + Fn?2, F1 = 1，F2 = 1.
那么其12项为:
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
因此第12项，F12，是第一个包含三位数字的项。
斐波那契数列中第一个包含1000位数字的项是第几项？
>>> limit=10**999 >>> i=1 >>> a=1 >>> b=1 >>> while b < limit: a,b=a+b,a i+=1 >>> i 478226 Reciprocal cycles
分子为1的分数称为单分数。分母是2到10的单分数用十进制表示如下：
1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1
其中0.1(6) 表示 0.166666...,因此它又一个长度为1的循环圈。可以看出1/7拥有一个6位的循环圈。
找出小于1000的数字d，1/d 的十进制表示含有最长的循环圈
论坛这页打不开了-_-||
27 Quadratic primes
欧拉曾发表过一个著名的二次公式：
n2 + n + 41
这个公式对于0到39的连续数字能够产生40个质数。但是当 n = 40时，402 + 40 + 41 = 40(40 + 1) + 41能够被41整除。当n = 41时, 412 + 41 + 41显然也能被41整除。
利用计算机，人们发现了一个惊人的公式：n2 ? 79n + 1601。这个公式对于n = 0 到 79能够产生80个质数。这个公式的系数，?79 和1601的乘积是?126479。
考虑如下形式的二次公式：
n2 + an + b, 其中|a| < 1000， |b| < 1000
其中|n| 表示 n 的绝对值。
例如， |11| = 11， |?4| = 4
对于能够为从0开始的连续的n产生最多数量的质数的二次公式，找出该公式的系数乘积。
#include<iostream>
#define MAXN 2000001
using namespace std;
int bprime[MAXN]={0};
int Count(int a,int b)
{
int tmp=b,n=0;
while(tmp>0&&!bprime[tmp])
{
n++;
tmp=n*n+a*n+b;
}
return n;
}
int main()
{
for (int i=2;i<2000;i++)
if(!bprime[i])
for(int j=2;i*j<=MAXN;j++)
bprime[i*j]=1;
int len=0;
int product=0;
for(int a=-999;a<1000;a++)
for(int b=2;b<999;b++)
{
int tmp=Count(a,b);
if(!bprime[b]&&tmp>len)
{
len=tmp;
product=a*b;
}
}
cout<<product<<" "<<len<<endl;
return 0;
}
28 Number spiral diagonals从数字1开始向右顺时针方向移动，可以得到如下的5×5的螺旋：
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
可以算出对角线上数字之和是101.
1001×1001的螺旋中对角线上数字之和是多少？推推公式
>>>limit=(1001-1)/2 >>>sum([(n*4+2)**2-12*n for n in range(1,limit+1,1) ])+129 Distinct powers
考虑 a^b 在 2 ≤ a ≤ 5，2 ≤ b ≤ 5下的所有整数组合：
2^2=4, 2^3=8, 2^4=16, 2^5=32
3^2=9, 3^3=27, 3^4=81, 3^5=243
4^2=16, 4^3=64, 4^4=256, 4^5=1024
5^2=25, 5^3=125, 5^4=625, 5^5=3125
如果将这些数字排序，并去除重复的，我们得到如下15个数字的序列：
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
a^b 在 2 ≤ a ≤ 100，2 ≤ b ≤ 100 下生成的序列中有多少个不同的项？
import itertools print len(set(a**b for a,b in itertools.product(xrange(2,101), repeat=2)))30 Digit fifth powers
令人惊奇的，只有三个数能够写成它们各位数的四次方之和：
1634 = 1^4 + 6^4 + 3^4 + 4^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 9^4 + 4^4 + 7^4 + 4^4
1 = 14没有被算作在内因为它不是一个和。
这些数字的和是 1634 + 8208 + 9474 = 19316.
找出所有能被写成各位数字五次方之和的数之和
>>> ans=0 >>> for x in xrange(2,10*9**5): sm=0 for i in str(x): sm+=int(i)**5 if sm==x: ans+=sm >>> ans 44383931 Coin sums
在英国，货币是由英镑￡，便士p构成的。一共有八种钱币在流通：
1p, 2p, 5p, 10p, 20p, 50p, ￡1 (100p) 和 ￡2 (200p).
要构造￡2可以用如下方法：
1×￡1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
允许使用任意数目的钱币，一共有多少种构造￡2的方法？简单的动态规划，我用生成函数做的
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int cnt=201;
int mul[cnt]={0};
int tmp[cnt]={0};
int fact[]={1,2,5,10,20,50,100,200};//8
int main()
{
mul[0]=1;
for(int i=0;i<8;i++)
{
for(int i=0;i<cnt;i++)
tmp[i]=0;
for(int j=0;j<cnt;j+=fact[i])//j power
{
for(int k=0;k<cnt;k++)//k power
if(k+j>=cnt)
break;
else
tmp[k+j]+=mul[k];
}
copy(tmp,tmp+cnt,mul);
}
cout<<mul[cnt-1]<<endl;
return 0;
}32 Pandigital products
如果一个n位数使用了1到n中每个数字且只使用了一次，我们称其为pandigital。例如，15234这个五位数，是1到5pandigital的。
7254是一个不寻常的数，因为：39 × 186 = 7254这个算式的乘数，被乘数和乘积组成了一个1到9的pandigital组合。
找出所有能够组合成1到9pandigital的乘法算式中乘积的和。
提示: 有的乘积数字能够被多个乘法算式得到，所以在计算时要记得只计算它们一次。
#include<iostream>
#include<set>
using namespace std;
int len(int n )
{
if(!n) return 0;
int i=0;
while(n)
{
n/=10;
i++;
}
return i;
}
bool ok(int a,int b=0,int c=0)
{
bool have[10]= {0};
int num=1;
if(b) num=2;
if(c) num=3;
int tmp[]= {a,b,c};
for(int i=0; i<num; i++)
{
int m=tmp[i];
while(m)
if(have[m%10])
return false;
else
{
have[m%10]=true;
m/=10;
}
}
if(have[0]) return false;
if(!b) return true;
return len(a)+len(b)+len(c)==9;
}
set<int> se;
int main()
{
long long ans=0;
for(int i=1; i<9900; i++)
if(ok(i))
for(int j=1; j<i; j++)
if(i*j>10000)
break;
else if(ok(i,j,i*j))
se.insert(i*j);
for(set<int>::const_iterator it=se.begin(); it!=se.end(); ++it)
ans+=*it;
cout<<ans<<endl;
return 0;
}33 Digit cancelling fractions分数 49/98 是一个奇怪的分数：当一个菜鸟数学家试图对其进行简化时，他可能会错误地可以认为通过将分子和分母上的9同时去除得到 49/98 = 4/8。但他得到的结果却是正确的。
我们将30/50 = 3/5这样的分数作为普通个例。
一共有四个这样的非普通分数，其值小于1，并且包括分子和分母都包括2位数。
如果将这四个分数的乘积约分到最简式，分母是多少？
>>> for x in xrange(1,100): for y in xrange(x+1,100): a=x/10 b=x%10 c=y/10 d=y%10 if b==c and x*d==y*a and d<>0: ans[0]*=a ans[1]*=d ans=[ans[0]/gcd(ans[0],ans[1]),ans[1]/gcd(ans[0],ans[1])] >>> ans [1, 100]34 Digit factorials
145 是一个奇怪的数字, 因为 1! + 4! + 5! = 1 + 24 + 120 = 145.
找出所有等于各位数字阶乘之和的数字之和。
注意: 因为 1! = 1 和 2! = 2 不是和的形式，所以它们不算在内。
>>> fc=[fac(x) for x in range(0,10)] >>> ans=0 >>> for i in xrange(10,9999999): tmp=0 for x in str(i): tmp+=fc[int(x)] if i==tmp: ans+=tmp >>> ans 40730
#include<iostream>
using namespace std;
int fac[]={1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int sum(int n)
{
int ans=0;
while(n)
{
ans+=fac[n%10];
n/=10;
}
return ans;
}
int main()
{
int ans=0;
for(int i=10;i<10000000;i++)
if(i==sum(i))
ans+=i;
cout<<ans<<endl;
return 0;
}35 Circular primes我们称197为一个循环质数，因为它的所有轮转形式: 197, 971和719都是质数。
100以下有13个这样的质数: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 和97.
100万以下有多少个循环质数？
#include<iostream>
#include<algorithm>
#define MAXN 2000001
using namespace std;
int bprime[MAXN]={0};
bool check(int n)
{
if(bprime[n]) return false;
int tmp[10],cnt=0;
while(n)
{
tmp[cnt++]=n%10;
n/=10;
}
reverse(tmp,tmp+cnt);
for(int i=1;i<cnt;i++)
{
int k=0,tm=0;
for(int j=i;k<cnt;j=(j+1)%cnt,k++)
tm=tm*10+tmp[j];
if(bprime[tm]) return false;
}
return true;
}
int main()
{
for (int i=2;i<2000;i++)
if(!bprime[i])
for(int j=2;i*j<=MAXN;j++)
bprime[i*j]=1;
long long ans=0;
for(int i=2;i<1000000;i++)
if(check(i))
ans+=1;
cout<<ans<<endl;
return 0;
}
36 Double-base palindromes十进制数字585 = 10010010012 (二进制),可以看出在十进制和二进制下都是回文（从左向右读和从右向左读都一样）。
求100万以下所有在十进制和二进制下都是回文的数字之和。
（注意在两种进制下的数字都不包括最前面的0）
sum([x for x in xrange(1,1000001) if str(x) ==str(x)[::-1] and bin(x)[2::]==bin(x)[2::][::-1] ])37 Truncatable primes
3797这个数很有趣。它本身是质数，而且如果我们从左边不断地裁去数字，得到的仍然都是质数：3797,797,97,7。而且我们还可以从右向左裁剪：3797,379,37,3，得到的仍然都是质数。
找出全部11个这样从左向右和从右向左都可以裁剪的质数。
注意：2,3,5和7不被认为是可裁剪的质数
#include<iostream>
#define MAXN 1000001
using namespace std;
bool bprime[MAXN]={0};
bool check(int n)
{
int digit[11]={0},cnt=0;
while(n)
{
if(bprime[n]) return false;
digit[cnt++]=n%10;
n/=10;
}
int base=1;
for(int i=0;i<cnt;i++)
{
n=n+digit[i]*base;
base*=10;
if(bprime[n]) return false;
}
return true;
}
int main()
{
bprime[0]=bprime[1]=true;
for (int i=2;i<10000;i++)
if(!bprime[i])
for(int j=2*i;j<=MAXN;j+=i)
bprime[j]=true;
long long ans=0;
int cnt=0;
for(int i=11;i<MAXN&&cnt<11;i++)
if(!bprime[i]&&check(i))
{
ans+=i;
cnt++;
}
cout<<ans<<endl;
return 0;
}
38 Pandigital multiples
将192与1,2,3分别相乘得到：
192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
将这三个乘积连接起来我们得到一个1到9的pandigital数， 192384576。我们称 192384576是192和 (1,2,3)的连接积。
通过将9与1,2,3,4和5相乘也可以得到pandigital数：918273645，这个数是9和(1,2,3,4,5)的连接积。
用一个整数与1,2, ... , n（n大于1）的连接积构造而成的1到9pandigital数中最大的是多少？
ans=0 for i in xrange(10000): tmp='' j=1 while len(tmp) <9: tmp=tmp+str(j*i) j+=1 if len(tmp)==9 and not '0' in tmp and len(set(tmp))==9 and int(tmp)>ans: ans=int(tmp) print ans39 Integer right triangles
如果p是一个直角三角形的周长，三角形的三边长{a,b,c}都是整数。对于p = 120一共有三组解：
{20,48,52}, {24,45,51}, {30,40,50}
对于1000以下的p中，哪一个能够产生最多的解？
#include<iostream>
using namespace std;
int cnt[1000+5]= {0};
int main()
{
for(int i=1; i<500; i++)
for(int j=i; j<500; j++)
for(int k=j; k<500; k++)
if(i*i+j*j==k*k && i+j+k<=1000)
cnt[i+j+k]++;
int ans=0,len=0;
for(int i=1; i<=1000; i++)
if(cnt[i]>len)
len=cnt[ans=i];
cout<<ans<<endl;
return 0;
}40 Champernowne‘s constant0.123456789101112131415161718192021...
可以看出小数部分的第12位是1。
如果用dn表示这个数小数部分的第n位，找出如下表达式的值：
d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000 ，代码又丢了
irn = ''.join([`n` for n in range(200000)]) print reduce(lambda x, y: x*y, [int(irn[i]) for i in [10**j for j in range(7)]])41 Pandigital prime
如果一个数字将1到n的每个数字都使用且只使用了一次，我们将其称其为一个n位的pandigital数。例如，2143是一个4位的pandigital数，并且是一个质数。
最大的n位pandigital质数是多少？
#include<iostream>
#define MAXN 8000001
using namespace std;
int bprime[MAXN]= {0};
bool used[8]={0};
int ans=0;
int level;
void dfs(int lv=0,int n=0)
{
if(lv==level&&!bprime[n]&&n>ans)
ans=n;
if(lv==level) return ;
for(int i=1;i<level+1;i++)
if(!used[i])
{
used[i]=true;
dfs(lv+1,n*10+i);
used[i]=false;
}
}
int main()
{
for(int i=2;i<3000;i++)
if(!bprime[i])
for(int j=i*2;j<MAXN;j+=i)
bprime[j]=true;
for(level=4;level<8;level++)
{
for(int i=0;i<8;i++)
used[i]=false;
dfs();
}
cout<<ans<<endl;
return 0;
}42 Coded triangle numbers三角形数序列中第 n 项的定义是： tn = ?n(n+1); 因此前十个三角形数是:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
通过将一个单词中每个字母在字母表中的位置值加起来，我们可以将一个单词转换为一个数。例如，单词SKY的值为19 + 11 + 25 = 55 = t10。如果单词的值是一个三角形数，我们称这个单词为三角形单词。
words.txt (右键另存为)是一个16K的文本文件，包含将近两千个常用英语单词。在这个文件中，一共有多少个三角形词？
>>> word=[" ... ""]
>>> tri=set([x*(x+1)/2 for x in xrange(1,100)])
>>> ans=0
>>> for x in word:
tmp=0
for i in x:
tmp+=ord(i)-ord('A')+1
if tmp in tri:
ans+=1
>>> ans
162
>>> 43 Sub-string divisibility1406357289是一个pandigital数，因为它包含了0到9之间每个数字且只包含了一次。此外它还有一个有趣的子串整除性质。
令d1表示其第一位数字，d2表示第二位，以此类推。这样我们可以得到：
d2d3d4=406 能被 2 整除
d3d4d5=063 能被 3 整除
d4d5d6=635 能被 5 整除
d5d6d7=357 能被 7 整除
d6d7d8=572 能被 11 整除
d7d8d9=728 能被 13 整除
d8d9d10=289 能被 17 整除
求所有具有如上性质的0到9pandigital数
#include<iostream>
#include<algorithm>
using namespace std;
int digit[10]={0,1,2,3,4,5,6,7,8,9};
bool check()
{
if(digit[0]==0) return false;
if(digit[3]&1)return false;
if((digit[4]+digit[3]+digit[2])%3) return false;
if(digit[5]%5) return false;
if((digit[4]*100+digit[5]*10+digit[6])%7) return false;
if((digit[5]*100+digit[6]*10+digit[7])%11) return false;
if((digit[6]*100+digit[7]*10+digit[8])%13) return false;
if((digit[7]*100+digit[8]*10+digit[9])%17) return false;
return true;
}
int main()
{
long long ans=0;
for(int i=0;i<3628800;i++)
{
next_permutation(digit,digit+10);
if(check())
{
long long tmp=0;
for(int i=0;i<10;i++)
{
cout<<digit[i];
tmp=tmp*10+digit[i];
}
cout<<endl;
ans+=tmp;
}
}
cout<<ans<<endl;
}
44 Pentagon numbers
五角数通过如下公式定义：Pn=n(3n?1)/2。前十个五角数是：
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
可以看出P4 + P7 = 22 + 70 = 92 = P8. 但是它们的差70 ? 22 = 48却不是五角数。
找出最小的五角数对Pj 和 Pk,， 使得它们的和与差都是五角数，并且D = |Pk ? Pj| 取到最小。这时D的值是多少?
>>> sn5=set([x*(3*x-1)/2 for x in range(1,5000)]) >>> for x in sn5: for y in sn5: if (x+y) in sn5 and(x-y) in sn5: print x-y
45 Triangular, pentagonal, and hexagonal
三角数，五角数和六角数分别通过以下公式定义：
三角数 Tn=n(n+1)/21, 3, 6, 10, 15, ...
五角数 Pn=n(3n?1)/21, 5, 12, 22, 35, ...
六角数 Hn=n(2n?1)1, 6, 15, 28, 45, ...
可以证实 T285 = P165 = H143 = 40755.
找出这之后的下一个既是五角数又是六角数的三角数
>>> limit=100000 >>> n3=set([x*(x+1)/2 for x in xrange(1,limit)]) >>> n5=set([x*(3*x-1)/2 for x in xrange(1,limit)]) >>> n6=set([n*(2*n-1) for n in xrange(1,limit)]) >>> ans=n3.intersection(n5.intersection(n6)) >>> ans set([1, 40755, 1533776805])46 Goldbach‘s other conjecture
Christian Goldbach 提出每个奇合数都可以写作一个质数与一个平方数的二倍之和：
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
但是这个推测是错误的。
最小的不能写作一个质数与一个平方数的二倍之和的奇合数是多少？
#include<iostream>
#include<math.h>
using namespace std;
const int limit=10000001;
bool bprime[limit]={0};
int prime[limit/8]={0};
int nprime=0;
bool isprime(int n)
{
if(n<limit) return bprime[n]==false;
int i=0;
while(prime[i]*prime[i]<=n)
{
if(n%prime[i]==0) return false;
i++;
}
return true;
}
bool issquare(int n)
{
int tmp=sqrt(n);
return tmp*tmp==n;
}
bool check(int n)
{
for(int i=0;prime[i]<n;i++)
{
int tmp=n-prime[i];
if((tmp&1)==0&&issquare(tmp>>1))
return true;
}
return false;
}
int main()
{
for(int i=2;i<1000;i++)
if(!bprime[i])
for(int j=i*2;j<limit;j+=i)
bprime[j]=true;
for(int i=2;i<limit;i++)
if(!bprime[i])
prime[nprime++]=i;
for(int i=3;;i+=2)
if(!isprime(i)&&!check(i))
{
cout<<i<<endl;
return 0;
}
return 0;
}47 Distinct primes factors最小的两个具有两个不同质数因子的连续整数是：
14 = 2 × 7
15 = 3 × 5
最小的三个具有三个不同质数因子的连续整数是：
644 = 22 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.
找出最小的四个具有四个不同质数因子的整数。它们之中的第一个是多少？
#include<iostream>
using namespace std;
const int limit=1000001;
bool bprime[limit]={0};
int prime[limit/8]={0};
int nprime=0;
bool check(int n)
{
int i=0,cnt=0;
if(n<limit && !bprime[n]) return false;
while(prime[i]*prime[i]<=n)
{
if(n%prime[i]==0)
{
++cnt;
while(n%prime[i]==0) n/=prime[i];
if(cnt>4)
return false;
}
i++;
}
if(n!=1) ++cnt;
return cnt==4;
}
int main()
{
for(int i=2;i<1000;i++)
if(!bprime[i])
for(int j=i*2;j<limit;j+=i)
bprime[j]=true;
for(int i=2;i<limit;i++)
if(!bprime[i])
prime[nprime++]=i;
int n=2;
int ans=0;
while(true)
{
int oldn=n;
while(check(n))
n++;
if(n-oldn>=4)
{
cout<<oldn<<endl;
return 0;
}
n++;
}
return 0;
}48 Self powers
1^1 + 2^2 + 3^3 + ... + 1000^1000的最后十位是什么？
print sum([(x**x)%(10**10) for x in range(1,1001)])%(10**10)49 Prime permutations
1487, 4817, 8147这个序列，每个比前一个递增3330，而且这个序列有两个特点：1. 序列中的每个数都是质数。2. 每个四位数都是其他数字的一种排列。
1，2，3位组成的三个质数的序列中没有具有以上性质的。但是还有另外一个四位的递增序列满足这个性质。
如果将这另外一个序列的三个数连接起来，组成的12位数字是多少？
#include<iostream>
#include<algorithm>
#define MAXN 2000001
using namespace std;
int bprime[MAXN]= {0};
bool check(int a,int b,int c)
{
int digit[4];
for(int i=0; i<4; i++)
{
digit[i]=a%10;
a/=10;
}
int bok=0,cok=0;
for(int i=0; i<4; i++)
for(int j=0; j<4; j++)
{
if(i==j) continue;
for (int k=0; k<4; k++)
{
if(i==k||j==k) continue;
for(int t=0; t<4; t++)
{
if(t==i||t==j||t==k) continue;
int tmp=digit[i]*1000+digit[j]*100+digit[k]*10+digit[t];
if(tmp==b) bok++;
if(tmp==c) cok++;
}
}
}
return (cok&&bok);
}
int prime[MAXN/9];
int nprime=0;
int main()
{
for (int i=2; i<2000; i++)
if(!bprime[i])
for(int j=2; i*j<=MAXN; j++)
bprime[i*j]=1;
for(int i=1000; i<9999; i++)
if(!bprime[i])
prime[nprime++]=i;
for(int i=0; i<nprime; i++)
for(int j=i+1; j<nprime; j++)
if(!bprime[prime[j]*2-prime[i]]&&check(prime[i],prime[j],prime[j]*2-prime[i]))
cout<<"Bingo "<<prime[i]<<" "<<prime[j]<<" "<<prime[j]*2-prime[i]<<endl;
return 0;
}
50 Consecutive prime sum41这个质数，可以写作6个连续质数之和：
41 = 2 + 3 + 5 + 7 + 11 + 13
这是100以下的最长的和为质数的连续质数序列。
1000以下最长的和为质数的连续质数序列包含21个项，和为953.
找出100万以下的最长的何为质数的连续质数序列之和。
100万以下的哪个质数能够写成最长的连续质数序列？
#include<iostream>
#define MAXN 1000001
using namespace std;
int bprime[MAXN]={0};
int prime[MAXN/9];
int nprime=0;
int main()
{
for (int i=2;i<2000;i++)
if(!bprime[i])
for(int j=2;i*j<=MAXN;j++)
bprime[i*j]=1;
for(int i=2;i<MAXN;i++)
if(!bprime[i])
prime[nprime++]=i;
int ans=0,sum,len=0;
for(int i=0;i<nprime;i++)
{
sum=0;
int j;
for(j=i;j<nprime;j++)
{
sum+=prime[j];
if(sum>=MAXN) break;
if(!bprime[ sum ] &&len <=j-i)
{
len=j-i+1;
ans=sum;
}
}
}
cout<<ans<<endl;
return 0;
}这Ctrl +C,Ctrl+V终于给搞完了，这个只是为了留下代码，Project Euler 太坑了论坛的回复竟然会删除
另外Project Euler论坛回复，编辑框没有CSDN这么方便，添加代码要自己加标签
‘[code=C++] 代码 [/code]‘ 这样就可以了，别的语言类似。
Project-Euler problem 1-50