Problem 37

问题描述：

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

 

 

解决问题：

package projecteuler;

import java.util.Arrays;

public class Problem37 {

	public static boolean prime[] ;
	public static int UP = 11;
	
	public static boolean IsPrime(int number) {
		boolean result = true;

		if(number==1||number==2){
			return true;
		} else if (number % 2 == 0) {
			return true;
		} else {
			int middle = (int) Math.sqrt(number);
			for (int i = 3; i <= middle; i += 2) {
				if (number % i == 0) {
					return false;
				}
			}
		}
		return true;
	}

	public static boolean IsNumber(int number){
		
		int tmp = number;
		int max = 10;
		int n;
		do{
			n = tmp%max;
//			System.out.println("1:"+tmp%max);
			if(!prime[n]){
				return false;
			}
			max = max*10;
		}while(n!=number);
		max = max/100;
//		System.out.println("Max:"+max);
		do{
			n = tmp/max;
//			System.out.println("2:"+tmp/max);
			if(!prime[n]){
				return false;
			}
			max = max/10;;
		}while(n!=number);
		return true;

	}
	
	public static void main(String[] args){
		long t1 = System.currentTimeMillis();
		prime = new boolean[3000000];
		Arrays.fill(prime, false);
		for (int i = 3; i < 3000000; i=i+2) {
			if(IsPrime(i))
				prime[i] = true;
		}
		prime[2] = true;
		int n = 11;
		int count = 0;
		int sum = 0;
		do{
			if(IsNumber(n)){
				sum +=n;
				count++;
				System.out.println(n);
			}
			n = n+2;
		}while(count<UP);
		long t2 = System.currentTimeMillis();
		System.out.println("Sum:"+sum);
		
		System.out.println(t2-t1);
	}
}