Problem 37(Truncatable primes)

Problem 37(Truncatable primes)

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.

 

In Python:

import math
import time

def isprime(n):
    if n == 1:
        return False
    else:
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                return False
        return True

def sieve(n):
    primeList = []
    primeCheck = [1 for i in range(2, n + 1)]
    for i in range(2, n):
        if primeCheck[i - 2] == 1:
            primeList.append(i)
            for j in range(2, int(n // i) + 1):
                primeCheck[i * j - 2] = 0
    return primeList

startTime = time.time()
count = 0
result = 0
primeList = sieve(10 ** 6)

for prime in primeList:
    dig = len(list(str(prime)))
    check = 0
    if dig > 1:
        for i in range(1, dig):
            if isprime(int(str(prime)[i:])) is False:
                check += 1
                break
        if check == 1: continue
        for j in range(1, dig):
            if isprime(int(str(prime)[:-j])) is False:
                check += 1
                break
        if check == 0:
            result += prime
print(result)
print(time.time() - startTime, "seconds")

Run time: 1.2444651126861572 seconds

 

In Java:

package project_euler31_40;

import java.util.ArrayList;

public class Euler37 {
	public static Boolean isprime(int n) {
		if (n == 1) {
			return false;
		}
		for (int i = 2; i < (int)Math.sqrt(n) + 1; i++) {
			if (n % i == 0) {
				return false;
			}
		}
		return true;
	}
	public static void main(String[] args) {
		long startTime = System.currentTimeMillis();
		int n = (int) Math.pow(10, 6);
		String subS = "";
		int subN = 0;
		int dig = 0;
		int check = 0;
		int result = 0;
		ArrayList<Integer> primeList = new ArrayList<Integer>();
		ArrayList<Integer> primeCheck = new ArrayList<Integer>();
		
		for (int i = 2; i < n + 1; i++) {
			primeCheck.add(1);
		}
		for (int i = 2; i < n; i++) {
			if (primeCheck.get(i - 2) == 1) {
				primeList.add(i);
				for (int j = 2; j < Math.floorDiv(n, i) + 1; j++) {
					primeCheck.set(i * j - 2, 0);
				}
			}
		}
		for (int prime : primeList) {
			dig = (int)Math.log10(prime) + 1;
			check = 0;
			if (dig > 1) {
				for (int i = 1; i < dig; i++) {
					subS = Integer.toString(prime).substring(i);
					subN = Integer.parseInt(subS);
					if (isprime(subN) == false) {
						check ++;
						break;
					}
				}
				if (check == 1) {
					continue;
				}
				for (int j = dig; j > 0; j--) {
					subS = Integer.toString(prime).substring(0, j);
					subN = Integer.parseInt(subS);
					if (isprime(subN) == false) {
						check ++;
						break;
					}
				}
				if (check == 0) {
					result += prime;
				}
			}
		}
		System.out.println(result);
		long endTime = System.currentTimeMillis();
		System.out.println((double)(endTime - startTime)/(double)1000 + "seconds");
	}
}

Run time: 0.516seconds

 

Solution: 748317