Project Euler 50 Consecutive prime sum

题意：

素数41可以写成六个连续素数的和：

41 = 2 + 3 + 5 + 7 + 11 + 13

在小于一百的素数中，41能够被写成最多的连续素数的和。

在小于一千的素数中，953能够被写成最多的连续素数的和，共包含连续21个素数。

在小于一百万的素数中，哪个素数能够被写成最多的连续素数的和？

思路：首先打出100000以内的素数表，然后计算出所有从第一个素数到 j 的和，然后枚举两个端点判断是否符合要求即可

/*************************************************************************

    > File Name: euler050.c

    > Author:    WArobot

    > Blog:      http://www.cnblogs.com/WArobot/

    > Created Time: 2017年07月01日 星期六 19时43分19秒

 ************************************************************************/

#include <stdio.h>

#include <inttypes.h>

#define MAX_N 1000000

int32_t prime[MAX_N + 10] = {0};

int32_t primeList[MAX_N + 10] = {0};

int64_t sum[MAX_N + 10] = {0};

void Init() {

	for (int32_t i = 2 ; i <= MAX_N ; i++) {

		if (!prime[i]) {

			primeList[++primeList[0]] = i;

		}

		for (int32_t j = 1 ; j <= primeList[0] ; j++) {

			if (i * primeList[j] > MAX_N)	break;

			prime[i * primeList[j]] = 1;

			if (i % primeList[j] == 0)		break;

		}

	}

	for (int32_t i = 1 ; i <= primeList[0] ; i++) {

		sum[i] = sum[i - 1] + primeList[i];

	}

}

int32_t main() {

	Init();

	int32_t maxP = 953 , maxL = 21;

	for (int32_t i = 1 ; i < primeList[0] ; i++) {

		for (int32_t j = i + maxL ; j <= primeList[0] ; j++) {

			if (sum[j] - sum[i] > MAX_N)	break;

			if (prime[sum[j] - sum[i]])		continue;

			if (maxL < j - i){

				maxL = j - i;

				maxP = sum[j] - sum[i];

			}

		}

	}

	printf("maxL = %d , maxP = %d\n",maxL , maxP);

	return 0;

}

巴特西

Project Euler 50 Consecutive prime sum

最新文章

热门文章