Prime triplets题号：196 难度： 65 中英对照

Build a triangle from all positive integers in the following way:

1
2  3
4  5  6
7  8  9 10
11 12 13 14 15
16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 32 33 34 35 36
37 38 39 40 41 42 43 44 45
46 47 48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63 64 65 66
. . .

Each positive integer has up to eight neighbours in the triangle.

A set of three primes is called a prime triplet if one of the three primes has the other two as neighbours in the triangle.

For example, in the second row, the prime numbers 2 and 3 are elements of some prime triplet.

If row 8 is considered, it contains two primes which are elements of some prime triplet, i.e. 29 and 31.
If row 9 is considered, it contains only one prime which is an element of some prime triplet: 37.

Define S(n) as the sum of the primes in row n which are elements of any prime triplet.
Then S(8)=60 and S(9)=37.

You are given that S(10000)=950007619.

Find  S(5678027) + S(7208785).

Code

import java.math.BigInteger;

public final class p196 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

static public String run() {
return (solve(5678027) + solve(7208785))+"";
}

static long list[]=new long[8];
static long list2[]=new long[8];
static long list_n[]=new long[8];
static long list_n2[]=new long[8];

static long solve(long n){
long ans=0;
long start=(n-1)*n/2;
for(long i=start+1;i<=start+n;i++){
if(!prime(i)) continue;
int cnt=get(i,n,list,list_n);
boolean flag=true;
int count=1;
for(int j=0;j<cnt && flag && count<=2;j++) if(prime(list[j])){
int cnt2=get(list[j],list_n[j],list2,list_n2);
int count2=1;
for(int k=0;k<cnt2 && count2<=2;k++) if(prime(list2[k]))
count2++;
if(count2>=3) flag=false;
count++;
}
if(!flag || count>=3)
ans+=i;
i++;
}
return ans;
}

static int get(long i,long n,long list[],long list_n[]){
int cnt=0;
list[cnt]=i-n+1+0;	list_n[cnt]=n-1;	if(check(list[cnt],list_n[cnt])) cnt++;
list[cnt]=i-n+1+1;	list_n[cnt]=n-1;	if(check(list[cnt],list_n[cnt])) cnt++;
list[cnt]=i-n+1-1;	list_n[cnt]=n-1;	if(check(list[cnt],list_n[cnt])) cnt++;
//   	list[cnt]=i    +1;	list_n[cnt]=n  ;	if(check(list[cnt],list_n[cnt])) cnt++;
//  	list[cnt]=i    -1;	list_n[cnt]=n  ;	if(check(list[cnt],list_n[cnt])) cnt++;
list[cnt]=i+n  +0;	list_n[cnt]=n+1;	if(check(list[cnt],list_n[cnt])) cnt++;
list[cnt]=i+n  +1;	list_n[cnt]=n+1;	if(check(list[cnt],list_n[cnt])) cnt++;
list[cnt]=i+n  -1;	list_n[cnt]=n+1;	if(check(list[cnt],list_n[cnt])) cnt++;
return cnt;
}

static boolean check(long i,long n){
return n*(n-1)/2<i && i<=n*(n+1)/2;
}

static boolean prime(long n) {
if((n&1)==0) return false;
return prime(BigInteger.valueOf(n));
}

static boolean prime(BigInteger n) {
return n.isProbablePrime(8);
}

}
322303240771079935
156191ms