题目50：100万以下的哪个质数能够写成最多连续质数的和？
本帖最后由 欧拉计划 于 2015-5-30 01:41 编辑Consecutive prime sum
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 这个质数，可以写作 6 个连续质数之和：
41 = 2 + 3 + 5 + 7 + 11 + 13
这是 100 以下的最长的和为质数的连续质数序列。
1000 以下最长的和为质数的连续质数序列包含 21 个项，和为 953。
找出 100 万以下的最长的何为质数的连续质数序列之和。
100 万以下的哪个质数能够写成最长的连续质数序列？
本帖最后由 jerryxjr1220 于 2016-12-10 10:53 编辑
997651 从质数序列的第3位起 连续543个
def getPrime(n):
primes = *n
primes,primes=False,False
for (i, prime) in enumerate(primes):
if prime:
for j in range(i*i,n,i): primes = False
return
primes = getPrime(1000000)
def main():
n = 1000000
# set max window size
window = 1
while sum(primes[:window]) < n:
window += 1
# moving window
while window > 1:
# moving window start and end
start = 0
end = start + window
# move till the end of prime list
while end < len(primes):
# test: always true, is sum of primes
tmp = sum(primes)
# too big, skip
if tmp > n:
break
# test: is prime, < n
elif tmp < n and tmp in primes:
print ('found', window, tmp)
return
# sliding window
start += 1
end = start + window - 1
# try next window size
window -= 1
main()
import math
def Prime(x):
if x >1:
if x==2:
return True
if x%2==0:
return False
for i in range(3,int(math.sqrt(x)+1),2):
if x%i==0:
return False
return True
return False
count = 0
list1=[]
i = 1
while True:
if Prime(i):
if count+i<1000000:
count +=i
list1.append(i)
elif count +i>1000000:
break
i+=1
tmp = count
temp = count
if not Prime(count):
for i in range(len(list1)):
tmp -= list1
if Prime(tmp):
break
for i in range(1,len(list1)+1):
temp -= list1[-i]
if Prime(temp):
break
if tmp >temp:
print(tmp)
else:
print(temp)
结果：997651 本帖最后由 芒果加黄桃 于 2017-1-17 09:04 编辑
# encoding:utf-8
# 100万以内，可以写作最长的连续质数相加的质数
from time import time
def getPrimes(N):
primes = * N
primes, primes = False, False
for i, prime in enumerate(primes):
if prime:
for j in range(i * i, N, i):
primes = False
return
def euler050(N=1000000):
l_pr = getPrimes(N)
l_primes =
s_primes = set(l_pr)
for lenth in range(len(l_primes), 21, -1):
for i in range(0, len(l_primes) - lenth + 1):
sum_tmp = sum(l_primes)
if sum_tmp > N:
break
elif sum_tmp in s_primes:
print(sum_tmp, l_primes, len(l_primes))
return
pass
if __name__ == '__main__':
start = time()
euler050()
print('cost %.6f sec' % (time() - start))
997651 543
cost 0.423042 sec
本帖最后由 渡风 于 2017-6-14 17:19 编辑
%% Problem50.m
%最后编辑时间：2017-06-13 23:53 版本1.0
%找出100w以下的质数，使其为最长的连续质数的和
% 此代码使用matlab编程
% Problem50所用时间为0.10544秒
% Problem50的答案为997651
function Output = Problem50()
tic
% 刷出小于100w的质数
Limit = 1000000;
Judge = ones(1,Limit-1);
Judge(1) = 0;
for ii = 1:Limit-1
if Judge(ii) == 1
for jj = 2*ii : ii : Limit-1
Judge(jj) = 0;
end
end
end
PossiFactor = find(Judge == 1);
% 所有质数依次相加
StoreL = 0;
StoreNum = 0;
for ii =1:1:10
Vector = PossiFactor(ii:end);
PrimeSum = cumsum(Vector);
RealSum = PrimeSum( PrimeSum < Limit );
BiggestL = length(RealSum);
for jj = BiggestL : -1 :1
if isprime(RealSum(jj)) == 1
RealL = jj;
NowNum = RealSum(jj);
break
end
end
if RealL > StoreL
StoreL = RealL;
StoreNum = NowNum;
end
NextVector = PossiFactor(ii+1:end);
NextPrimeSum = cumsum(NextVector);
NextRealSum = NextPrimeSum( NextPrimeSum < Limit );
NextL = length(NextRealSum);
if StoreL > NextL
Output = StoreNum;
break
end
disp()
end
toc
disp('此代码使用matlab编程')
disp(['Problem50所用时间为',num2str(toc),'秒'])
disp(['Problem50的答案为',num2str(Output)])
end
用matlab暴力求解的结果：
最多可以被写成的连续素数的个数是：543
这个数字是：997651
时间已过 126.783852 秒。
>>
改进算法后的结果：
最多可以被写成的连续素数的个数是：543
这个数字是：997651
时间已过 55.165089 秒。
>>
{:10_266:}{:10_266:}{:10_266:}有空再来想想解法 最大值是：543
用时：0.5304034 秒
import time
def primes(N):
N_bool = * N
N_bool, N_bool = 0, 0
for i, j in enumerate(N_bool):
if j:
for k in range(i**2, N, i):
N_bool = 0
return
Primes = primes(1000000)
# 因为已知最值中最大是21，所以最大肯定大于21，此时如果值大于1000000/21 连续值肯定是超出1000000的;
l_primes =
s_primes = set(Primes)
length = len(l_primes)
# 方法一，将length 从大到小找
def cal():
for l in range(length, 21, -1):
for i in range(length - l):
tmp = sum(l_primes)
if tmp > 1000000:
break
else:
if tmp in s_primes:
return l
# 方法二，将length 从小到大去找，需借助中间变量，慢些，但是逻辑更清晰
def cal_2():
Max_loop = 21
for i in range(length):
for j in range(21, length-i):
tmp = sum(l_primes)
if tmp > 1000000:
break
else:
if tmp in s_primes and j > Max_loop:
Max_loop = j
return Max_loop
print("最大值是：{}\n用时：{} 秒".format(cal(), time.process_time())) 997651
Process returned 0 (0x0) execution time : 0.049 s
Press any key to continue.
欧氏筛
#include<iostream>
using namespace std;
const int M = 1e6;
int cnt = 0;
bool prime;
int factor;
void euler_sieve(){
prime = false;
for (int i = 2;i <= M;i++) prime = true;
for (int i = 2;i <= M;i++){
if (prime) factor[++cnt] = i;
for (int j = 1;j <= cnt && i*factor < M;j++){
prime] = false;
if (i % factor == 0) break;
}
}
}
int main(){
euler_sieve();
int ans = 0,maxl = -M;
for (int i = 1;i <= cnt;i++){
int sum = 0;
for (int j = i;j <= cnt;j++){
sum += factor;
if (sum >= M) break;
if (prime && j-i+1 > maxl){
ans = sum;
maxl = j-i+1;
}
}
}
cout << ans << endl;
return 0;
}
#include <stdio.h>
#include <math.h>
int check_prime(int);
int check_prime(int num)
{
if (num == 2)
{
return 1;
}
int i, j;
j = sqrt(num + 1);
for (i = 2; i <= j; i++)
{
if (num % i == 0)
{
return 0;
}
}
return 1;
}
int main()
{
int i, j, sum = 2;
for (i = 3; sum < 1000000; i += 2)//找出 质数之和小于 1000000的数
{
if (check_prime(i))
{
sum += i;
j = i;
}
}
sum = sum - j;//由于sum会1000000，所以减去最后加上的i
i = 2;
while (1)
{
if (check_prime(sum))//判断sum是否是质数
{
break;
}
else//不是就减去从2开始的质数
{
sum -= i;
}
i++;
while (check_prime(i) == 0)//判断i是否为质数
{
i++;
}
}
printf("%d\n", sum);
system("pause");
return 0;
}#include <stdio.h>
#include <math.h>
int check_prime(int);
int check_prime(int num)
{
if (num == 2)
{
return 1;
}
int i, j;
j = sqrt(num + 1);
for (i = 2; i <= j; i++)
{
if (num % i == 0)
{
return 0;
}
}
return 1;
}
int main()
{
int i, j, sum = 2;
for (i = 3; sum < 1000000; i += 2)//找出 质数之和小于 1000000的数
{
if (check_prime(i))
{
sum += i;
j = i;
}
}
sum = sum - j;//由于sum会1000000，所以减去最后加上的i
i = 2;
while (1)
{
if (check_prime(sum))//判断sum是否是质数
{
break;
}
else//不是就减去从2开始的质数
{
sum -= i;
}
i++;
while (check_prime(i) == 0)//判断i是否为质数
{
i++;
}
}
printf("%d\n", sum);
system("pause");
return 0;
}
997651 /*
答案：997651
耗时：0.0030334秒
*/
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
char cp;//素数表
int nps, nS;//素数表的前缀和
void get_ini(void)
{
//素数打表
memset(cp, 1, sizeof(cp));
cp = 0;
cp = 0;
for (int i = 2; i <= 1000; ++i)
{
if (cp == 0)
continue;
for (int j = i * i; j <= 1000000; j += i)
cp = 0;
}
//作素数数组
vector<int> vp;
vp.push_back(2);
for (int i = 3; i <= 1000000; i += 2)
{
if (cp == 1)
vp.push_back(i);
}
//求素数表的前缀和
nS = 0;
for (int i = 0; i < (int)vp.size(); ++i)
{
nS = nS + vp;
if (nS > 2000000)
break;
}
}
int main(void)
{
get_ini();
int nMaxLen = 0, k;
for (int i = 1; i <= nps; ++i)
{
for (int j = i - 1; j >= 0; --j)
{
int p = nS - nS;
if (p > 1000000)
break;
if (cp == 1)
{
if (i - j > nMaxLen)
{
nMaxLen = i - j;
k = p;
}
}
}
}
cout << k << endl;
return 0;
}
页:
[1]