オラ工程第37題:Truncatable primes

タイトルリンク:https://projecteuler.net/problem=37
11個の二重せん断質量数の和を求める
例えばhe 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.
考え方:1.ブール型素数配列2.この数が素数であれば、左剪断数が素数であるか否かを判断する.もし、右剪断数が素数であるか否かを判断する.もし、和を求めるなら
Javaコード:

package projecteuler31to40;

import java.util.Date;

class level37{

    void solve(){
        int Max_Value=1000000;
        int sum=0;
        boolean[] primes=PrimeArray(Max_Value);
        for(int i=10;i<Max_Value;i++){
            int num=i;
            boolean flag=true;
            if(primes[i]){
                while(num>10){
                 num=LeftToRight(num);
                 if(primes[num]==false){
                     flag=false;
                     break;
                 }
                }
                if(primes[num]==true && flag==true){
                    num=i;
                    while(num>10){
                        num=RightToLeft(num);
                        if(primes[num]==false){
                            flag=false;
                            break;
                        }
                    }
                    if(primes[num]==true && flag==true){
                        sum+=i;
// System.out.println(i);
                    }
                }
            }
        }
        System.out.println(sum);
    }
    int RightToLeft(int num){
        if(num<10)
            return num;
        return num/10;

    }
    int LeftToRight(int num){
        String str=String.valueOf(num);
        return Integer.parseInt(str.substring(1));
    }
    boolean[] PrimeArray(int num){
        boolean[] primes=new boolean[num+1];
        primes[2]=true;
        for(int i=3;i<num+1;++i)
            primes[i]=isPrime(i);
        return primes;
    }
    boolean isPrime(int num){
        for(int i=2;i<=Math.sqrt(num);i++){
            if(num%i==0)
                return false;
        }
        return true;
    }


}
public class Problem37 {


    public static void main(String[] args){
        Date beginTime=new Date();
        new level37().solve();//
        Date endTime=new Date();
        long Time=endTime.getTime()-beginTime.getTime();
        System.out.println("Time:"+Time/1000+"s"+Time%1000+"ms");
    }

}

結果:

748317
Time:0s493ms

11個の数は;

23
37
53
73
313
317
373
797
3137
3797
739397

結果から最大の上界は739397で、私が設定した上界は1000000で、人為的に上界を見つけることが重要です.
Pythonコード:

from time import time

def is_prime(x):
    if x in (1,4):
        return False
    if x in (2,3):
        return True 
    last_value=int(x**0.5)+1 
    for n in range(2,last_value):
        if x%n==0:
            return False
    return True

def trim(n,direction):
    if direction=='left':
        return(n[1:])
    else:
        return(n[:-1])

def check_left(n):
    if len(n)==1 and is_prime(int(n)):
        return True
    if is_prime(int(n)):
        return check_left(trim(n,'left'))
    else:
        return False

def check_right(n):
    if len(n)==1 and is_prime(int(n)):
        return True
    if is_prime(int(n)):
        return check_right(trim(n,'right'))
    else:
        return False

t=time()

sum=0
for num in range(11,10**6):
    p=str(num)
    if check_left(p)==True and check_right(p)==True:
        sum=sum+num

print sum

print("time is {0}".format(time() - t))

結果:
748317 time is 22.3920001984
このPythonはよく書けていて、私が問題解の中で見つけたので、少し直しました.
4つの関数が定義されています:1.素数2であるか否かを判定する.この文字列を反転します.左に切って、左に切った数を判断して、質数ではありませんか、意外にも再帰的に書いたのです.右に切る