Project Euler #37: Truncatable primes
Question
Answer : 748317
Hacker Rank Problem
Solution
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.
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.
Answer : 748317
Hacker Rank Problem
Solution
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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | import java.util.*; public class Solution { private static boolean[] prime = null; public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner in = new Scanner(System.in); int n = in.nextInt(); generatePrimes(); long res = 0; for(int i=11;i<n;i++) { if(prime[i] && isRightTruncatable(i) && isLeftTruncatable(i)) res+=i; } System.out.println(res); } public static boolean isLeftTruncatable(int n) { String s = String.valueOf(n); int i=0; while(i<s.length()) { if(!prime[Integer.valueOf(s.substring(i, s.length()))]) return false; i+=1; } return true; } public static boolean isRightTruncatable(int n) { while(n!=0) { if(!prime[n]) return false; n/=10; } return true; } public static void generatePrimes() { int limit = 1000000; prime = new boolean[limit+1]; prime[2] = true; prime[3] = true; int root = (int) Math.ceil(Math.sqrt(limit)); //Sieve of Atkin for prime number generation for (int x = 1; x < root; x++) { for (int y = 1; y < root; y++) { int n = 4 * x * x + y * y; if (n <= limit && (n % 12 == 1 || n % 12 == 5)) prime[n] = !prime[n]; n = 3 * x * x + y * y; if (n <= limit && n % 12 == 7) prime[n] = !prime[n]; n = 3 * x * x - y * y; if ((x > y) && (n <= limit) && (n % 12 == 11)) prime[n] = !prime[n]; } } for (int i = 5; i <= root; i++) { if (prime[i]) { for (int j = i * i; j < limit; j += i * i) { prime[j] = false; } } } } } |
Comments
Post a Comment