Problem 50
using System;
using System.Collections.Generic;
using System.Linq;
class Prime {
public static List<int> Sieve(int n) {
bool[] tab = new bool[n+1];
for (int i = 0; i < tab.Length; i++)
tab[i] = true;
int m = (int)Math.Sqrt(n+1);
for (int i = 3; i <= m; i++) {
if (tab[i]) {
for (int j = i+i; j <= n; j += i) {
tab[j] = false;
}
}
}
var primes = new List<int>();
primes.Add(2);
for (int i = 3; i <= n; i += 2) {
if (tab[i]) {
primes.Add(i);
}
}
return primes;
}
public static bool IsPrime(int n, List<int> primes) {
foreach (int p in primes) {
if (p * p > n) break;
if (n % p == 0)
return false;
}
return true;
}
}
class PE050 {
static void Main() {
int n = 1000000;
var primes = Prime.Sieve(n);
int maxlen = 0;
int ans = 0;
for (int i = 0; i < primes.Count; i++) {
int sum = 0;
for (int j = i; j < primes.Count; j++) {
sum += primes[j];
if (sum > n) break;
if (Prime.IsPrime(sum, primes)) {
if (maxlen < j - i + 1) {
maxlen = j - i + 1;
ans = sum;
}
}
}
}
Console.WriteLine("len:{0} prime:{1}", maxlen, ans);
}
}