Project Euler #47: Distinct primes factors
Question
Answer : 134043
Hacker Rank Problem
Solution
The first two consecutive numbers to have two distinct prime factors are:
14 = 2 × 7
15 = 3 × 5
The first three consecutive numbers to have three distinct prime factors are:15 = 3 × 5
644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.
Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?645 = 3 × 5 × 43
646 = 2 × 17 × 19.
Answer : 134043
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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | 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(); int k = in.nextInt(); int limit = 2500000; int root = (int) Math.ceil(Math.sqrt(limit)); prime = generatePrimes(root, limit); for(int i=2;i<=n;i++) { ArrayList<TreeSet> list = new ArrayList<TreeSet>(); if(!prime[i]) { for(int j=0;j<k;j++) { if(!prime[i+j]) { TreeSet s = primeFactorize(i+j); if(s.size()==k) list.add(s); else break; } else break; } } if(list.size()==k) System.out.println(i); } } public static TreeSet<Integer> primeFactorize(Integer n) { try { TreeSet<Integer> set = new TreeSet<Integer>(); for(int i=2;i<=n/i;i++) { while(n%i==0) { set.add(i); n/=i; } } if(n>1) set.add(n); return set; } catch(Exception e) { throw e; } } public static boolean[] generatePrimes(int root, int limit) { boolean[] prime = new boolean[limit+1]; prime[2] = true; prime[3] = true; //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; } } } return prime; } } |
Comments
Post a Comment