当前位置:首页 » Project Euler » 详细页

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).

Solution

直接暴力求解,时间较长,如果预处理素数会快一些。 暴力求解思路: 直接对第$n$行的所有数枚举,对枚举到的数字$x$,如果为素数,枚举其附近8个邻居,如果素数个数超过2个则符合题意,否则判断其为素数的邻居,继续枚举其附近8个邻居,如果素数个数超过2个则符合题意,可换下一个$x$。

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