β

Problem 50 Consecutive prime sum

JarvisChu's Blog | 猪之草房子 181 阅读

Problem

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?

分析

求小于100万的一个质数,这个质数等于N个连续的质数的和,且N最大。(为了叙述方便,我称这N个连续的质数为链)

方法1 对每一个质数统计其最大的链长,再找到链长最长的质数。【较慢,因为存在重复计算】

首先保存所有小于100万的质数。对于每个质数n,从2开始累加,如果一旦累加值等于n,此时的累加的质数链最长(不可能存在一个不是从2开始的质数链累加值等于n,而且链长更长),如果累加值不能得到n,那么从3开始重新累加,到了某个开始值的时候一定能有累加值等于n(至少当从n开始的链长为1的质数链就一定满足)。

问题的关键是如何快速的累加,保证不重复计算。对于每一个质数,获取其最长连续质数链的算法如下:

image

所有小于100万的质数2,3,4,5…保存在顺序容器中(如数组,列表)。对于每个质数n,要得到和等于它的最长连续质数链,则可从容器开头开始累加。

start指向质数链的开头,nxt指向质数链的结尾。sum统计当前质数链的长度。

初始时:start = nxt = 0,指向开头。sum = 0

然后执行如下循环:

如果sum = n,则表示找到了最长的连续质数链,返回质数链的开头位置start以及质数链的长度nxt-start. 循环终止。比如n = 2,此时start=0,nxt=1,sum = 2。

如果sum > n,则表示累加start到nxt后的累加值sum>n。此时的处理时本算法的一个关键。我们不用重新从start+1 位置开始统计。而是让sum 减去 start位置的数,然后start++。如果sum还大于n,则继续循环减去start位置的数,start++,直到sum <n.

如果sum <n,则sum加上链的后一个数,即nxt位置的数,然后nxt++。

上面过程Python代码如下,all_primes列表中存放了所有的质数。

#return the max length of prime n, and the start number
def calc_len(n):
	start, nxt, sum = 0, 0, 0     #start: the start index of the chain. nxt: the end index of the chain
	while True:
	if sum == n:
		ret = (all_primes[start], nxt - start) #if n=2,then nxt=1,start=0,len = nxt-start
		return ret
	elif sum > n:
		while sum > n:
			sum -= all_primes[start]
			start += 1
	else:
		sum += all_primes[nxt]
		nxt += 1

这个方法思路很清晰,但是运行较慢。因为对每个质数的计算过程大致相同,存在着重复计算问题。

方法2   用一种快速的方法获得100万以下的所有质数。然后依次统计以2开头的链,以3开头的链…找到最长的链长 【很快,<1s】

一种快速获取质数的方法:排除法。思路是这样的,如果i是质数,那么从i*i +k*i  (k=0,1,2…)都不是质数。

比如获取小于N的所有质数的方法如下:

vector<int> primes;
 
bool prime[N];
for(int i = 0 ; i < N ; i++) {
	prime[i] = true;   //i is initially regarding as a prime
}
 
for(int i = 2 ; i < N ; i++){
	if (prime[i]){
		primes.push_back(i);
		if(i <= (int)sqrt((double)N)){    // i*i <= N
			for(int t = i*i ; t<N ; t+=i){ //set all i*i+k*i -> false
				prime[t] = false;
			}
		}
	}
}

bool prime[N] 数组用来表示小于N的每个数是否是质数。初始时,全部设置为true,表示是质数。然后从i=2开始循环,如果prime[i] 是质数,那么就把prime[i] 保存到primes容器中,然后将i*i 开始的,每次加 i 的数都设置为不是质数。即,如果2是质数,那么就把从4开始,增量为2的所有数4,6,8,10,12…全部设为false,即不是质数。 接下来要统计最长的链,方法是这样的: 初始时设置最长链长为max_len=0,拥有最长链的质数是maxsum =0 , 从i=2开始,依次计算2,2+3,2+3+5,2+3+5+7,2+3+5+7+9…的值,如果当前值是质数,而且链的长度大于max_len,则更新max_len和max_sum。然后从i=3开始,再做相同的统计。依次类推,直到 i 是小于100万的最后一个质数。代码描述如下:

int maxlen = 0, maxsum = 0, cursum = 0;
for(int i = 2 ; i < primes.size() ; i++){
	cursum = 0;
	for(int j = i ; j < primes.size() ; j++)
	{
		cursum+=primes[j];
		if (cursum>=N)
			break;
		if ( prime[cursum] && j - i > maxlen )
		{
			maxlen = j-i;
			maxsum = cursum;
		}
	}
}

感谢 Xizario, P-E论坛第三页最后一个。

C\C++

方法1 [思路同分析] 保存所有小于100万的质数,计算每个质数的最长连续质数链长,找到链最长的质数。

#include "stdafx.h"
#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> all_primes;  //保存所有小于100万的质数
 
/************************************************************************ 
 * 判断n是否是质数
 ************************************************************************/
bool is_prime(int n){
	if (n <= 1)	{
		return false;
	}else if (n == 2 || n == 3){
		return true;
	}else if (n % 2 == 0){
		return false;
	}else{
		for (int i=3;i<=(int)sqrt((float)n);i++){
			if (n % i == 0){
				return false;
			}
		}
		return true;
	}
}
 
 
/************************************************************************ 
 * 返回质数n的最长链长
 ************************************************************************/
int calc_len(int n){
	int start=0,nxt=0,sum=0;
	while(true){
		if (sum == n){
			return nxt-start;
		}else if(sum > n){
			while(sum >n){
				sum -= all_primes[start++];
			}
		}else{
			sum += all_primes[nxt];
			nxt++;
		}
	}
	return 0;
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
	//find and store all the primes below one-millon
	for(int i=2;i<1000000;i++){
		if(is_prime(i)){
			all_primes.push_back(i);
		}
	}
 
	//iterate all the primes to find the one that has the longest chain 
	int max_len = 0,max_prime=0;
	
	vector<int>::iterator it;
	for(it=all_primes.begin();it!=all_primes.end();it++){
		int len = calc_len(*it);
		if(len > max_len){
			max_len = len;
			max_prime = *it;
			cout<<max_prime<<" "<<max_len<<endl;
		}
	}
 
	cout<<"The prime has longest chain is: "<<max_prime<<endl;
 
	return 0;
}

方法2   [思路同分析] 用一种快速的方法获得100万以下的所有质数。然后依次统计以2开头的链,以3开头的链…找到最长的链长 【很快,<1s】

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <math.h>
 
using namespace std;
 
#define N 1000000
 
int main()
{    
	int max = 0;
	vector<int> primes;
 
	bool prime[N];
	for(int i = 0 ; i < N ; i++) {
		prime[i] = true;   //i is initially regarding as a prime
	}
 
	for(int i = 2 ; i < N ; i++){
		if (prime[i]){
			primes.push_back(i);
			if(i <= (int)sqrt((double)N)){    // i*i <= N
				for(int t = i*i ; t<N ; t+=i){ //set all i*i+k*i -> false
					prime[t] = false;
				}
			}
		}
	}
 
	int maxlen = 0, maxsum = 0, cursum = 0;
	for(int i = 2 ; i < primes.size() ; i++){
		cursum = 0;
		for(int j = i ; j < primes.size() ; j++)
		{
			cursum+=primes[j];
			if (cursum>=N)
				break;
			if ( prime[cursum] && j - i > maxlen )
			{
				maxlen = j-i;
				maxsum = cursum;
			}
		}
	}
 
	cout<<maxsum<<endl;;
	return 0;
};

Python

方法1 [思路同分析] 保存所有小于100万的质数,计算每个质数的最长连续质数链长,找到链最长的质数。

#coding=utf-8

from math import sqrt

def is_prime(n):
    if n <= 1:
        return False
    elif n == 2 or n == 3:
        return True
    elif n % 2 == 0:
        return False
    else:
        for i in range(3, int(sqrt(n) + 1)):
            if n % i == 0:
                return False
        return True

#store all the primes below one-million
all_primes = [x for x in range(2,1000000) if is_prime(x)]
#print all_primes

#return the max length of prime n, and the start number
def calc_len(n):
    start, nxt, sum = 0, 0, 0     #start: the start index of the chain. nxt: the end index of the chain
    while True:
        if sum == n:
            ret = (all_primes[start], nxt - start) #if n=2,then nxt=1,start=0,len = nxt-start
            return ret
        elif sum > n:
            while sum > n:
                sum -= all_primes[start]
                start += 1
        else:
            sum += all_primes[nxt]
            nxt += 1
            #print start,nxt,sum,'c'

#find the longest chain of a prime below 1000000
max_len, start,max_prime = 0,0,0
for p in all_primes:
    ret = calc_len(p)
    if ret[1] > max_len:
        max_len, start, max_prime = ret[1], ret[0], p
        #print max_prime,max_len

print max_len, start, max_prime
方法2 [思路同分析] C\C++方法2 的Python版本
#coding=utf-8N=1000000
#find all the primes below one-million
prime = [True for i in range(1,N+1)]
primes = []
for i in range(2, N):
    if prime[i]:
        primes.append(i)
        t = i*i
        while t < N:
            prime[t] = False
            t += i
#find the longest chain
max_len, max_sum = 0, 0
prime_cnt = len(primes)
for i in range(2, prime_cnt):
    cur_sum = 0
    for j in range(i, prime_cnt):
        cur_sum += primes[j]
        if cur_sum >= N:
            break
        if prime[cur_sum] and (j - i > max_len):
            max_len, max_sum = j-i, cur_sum
print max_sum,max_len

答案

997651

注:链的长度为543,链的起始质数为7

作者:JarvisChu's Blog | 猪之草房子
Living and Coding
原文地址:Problem 50 Consecutive prime sum, 感谢原作者分享。

发表评论