Wednesday, November 16, 2016

Project Euler #39 Integer right triangles - Java 

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Solution {
    private static final int MAX_P = 5000000;
    private static final List<Integer> TRIPLET_LIST = new ArrayList<Integer>();
    private static final Set<Integer> TRIPLET_SET = new HashSet<Integer>();
    private static int[] SIEVE = new int[MAX_P + 1];
    private static boolean[] ISPRIME = new boolean[MAX_P + 1];

    public static void main(String[] args) {
        generateTriplets();
        getMaxPerimeter();
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            int n = scanner.nextInt();
            System.out.println(SIEVE[n]);
        }
        scanner.close();
    }

    private static void getMaxPerimeter() {
        TRIPLET_LIST.addAll(TRIPLET_SET);
        Collections.sort(TRIPLET_LIST);
        for (int i = 0; i <= MAX_P; i++) {
            SIEVE[i] = 0;
            ISPRIME[i] = true;
        }
        for (int p : TRIPLET_LIST) {
            for (int i = p * 2; i <= MAX_P; i += p) {
                ISPRIME[i] = false;
            }
        }
        for (int p : TRIPLET_LIST) {
            if (!ISPRIME[p]) {
                continue;
            }
            for (int i = p; i <= MAX_P; i += p) {
                SIEVE[i]++;
            }
        }
        int cur = 0;
        int curi = 0;
        for (int i = 0; i <= MAX_P; i++) {
            if (SIEVE[i] > cur) {
                cur = SIEVE[i];
                curi = i;
            }
            SIEVE[i] = curi;
        }
    }

    private static void generateTriplets() {
        for (int m = 3; m < 3000; m += 2) {
            int msq = m * m;
            for (int n = 1; n <= m; n += 2) {
                if (n != 1 && m % n == 0) {
                    continue;
                }
                int nsq = n * n;
                int a = m * n;
                int b = (msq - nsq) / 2;
                int c = (msq + nsq) / 2;
                int p = a + b + c;
                if (p > MAX_P) {
                    continue;
                }
                if (TRIPLET_SET.contains(p)) {
                    continue;
                }
                TRIPLET_SET.add(p);
            }
        }
    }

}
Posted by at
Labels: ,

Tuesday, November 15, 2016

Project Euler #38 Pandigital multiples - Java 

 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
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        generateAnswer(n, k);
        scanner.close();
    }

    private static void generateAnswer(int n, int k) {
        boolean DEBUG = false;
        for (int i = 2; i <= 10000; i++) {
            if (i > n) {
                break;
            }
            boolean[] count = new boolean[10];
            for (int j = 1; j <= k; j++) {
                count[j] = false;
            }
            // 13728
            // 27456
            boolean isPandigital = true;
            for (int j = 1; j <= 9; j++) {
                int prod = i * j;
                while (prod > 0) {
                    int d = prod % 10;
                    if (d > k || d == 0) {
                        isPandigital = false;
                        break;
                    }
                    if (count[d]) {
                        if (DEBUG) {
                            System.out.println("j=" + j + " prod=" + prod);
                        }
                        isPandigital = false;
                        break;
                    }
                    count[d] = true;
                    if (DEBUG) {
                        System.out.println("prod:" + prod);
                        System.out.println("d:" + d);
                        print(count, 9);
                    }
                    prod /= 10;
                }
                if (!isPandigital) {
                    if (DEBUG) {
                        System.out.println("first break");
                    }
                    break;
                }
                boolean allmarked = true;
                for (int l = 1; l <= k; l++) {
                    if (!count[l]) {
                        allmarked = false;
                    }
                }
                if (allmarked) {
                    if (DEBUG) {
                        System.out.println("second break");
                    }
                    j = 10;
                    break;
                }
            }
            if (isPandigital) {
                System.out.println(i);
            }
        }
    }

    /**
     * 9 18 27 36 45
     * 
     * @param arr
     * @param count
     */
    private static void print(boolean[] arr, int count) {
        for (int i = 1; i <= count; i++) {
            System.out.print(" " + arr[i] + " ");
        }
        System.out.println();
    }
}
Posted by at
Labels: ,

Project Euler #37 Truncatable primes - Java 

  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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
import java.util.ArrayList;
import java.util.Scanner;

public class Solution {

    private static ArrayList<Long> answer = new ArrayList<Long>();
    private static boolean[] sieve = new boolean[1000001];

    public static void main(String[] args) {
        // generateData();
        generateData2();
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long sum = 0;
        for (int i = 0; i < answer.size(); i++) {
            long d = answer.get(i);
            if (d > n) {
                break;
            }
            sum += d;
        }
        System.out.println(sum);
        scanner.close();
    }

    private static void generateData2() {
        for (int i = 0; i <= 1000000; i++) {
            sieve[(int) i] = true;
        }
        sieve[0] = false;
        sieve[1] = false;
        for (int i = 2; i <= Math.sqrt(1000000); i++) {
            if (sieve[i]) {
                for (int j = i * 2; j <= 1000000; j += i) {
                    sieve[j] = false;
                }
            }
        }
        for (long i = 11; i < 1000000; i += 2) {
            if (!sieve[(int) i]) {
                continue;
            }
            boolean DEBUG = false;
            long digits = (int) (Math.log10(i));
            long div = (int) Math.pow(10, digits);
            if (DEBUG) {
                System.out.println("div: " + div);
            }
            long t = i % div;
            boolean isDirty = true;
            while (div > 0 && t > 0) {
                if (DEBUG) {
                    System.out.println("t1: " + t);
                }
                if (!sieve[(int) t]) {
                    isDirty = false;
                    break;
                }
                div /= 10;
                if (div > 0) {
                    t = i % div;
                }
            }
            if (!isDirty) {
                continue;
            }
            t = (int) i / 10;
            while (t > 0) {
                if (DEBUG) {
                    System.out.println("t2: " + t);
                }
                if (!sieve[(int) t]) {
                    isDirty = false;
                    break;
                }
                t /= 10;
            }
            if (!isDirty) {
                continue;
            }
            System.out.println("d:" + i);
            answer.add(i);
        }
    }

    private static void generateData() {
        for (long i = 11; i < 1000000; i += 2) {
            long digits = (int) (Math.log10(i));
            long div = (int) Math.pow(10, digits);
            long t = i % div;
            boolean isDirty = true;
            while (div > 0 && t > 0) {
                if (!isPrime(t)) {
                    isDirty = false;
                    break;
                }
                div /= 10;
                if (div > 0) {
                    t = i % div;
                }
            }
            if (!isDirty) {
                continue;
            }
            t = (int) i / 10;
            while (t > 0) {
                if (!isPrime(t)) {
                    isDirty = false;
                    break;
                }
                t /= 10;
            }
            if (!isDirty) {
                continue;
            }
            System.out.println("d:" + i);
            answer.add(i);
        }
    }

    private static boolean isPrime(long n) {
        if (n <= 1) {
            return false;
        }
        if (n == 2 || n == 3) {
            return true;
        }
        if ((n & 1) != 1) {
            return false;
        }
        for (long i = 3; i <= Math.sqrt(n); i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}
Posted by at
Labels: ,

Project Euler #36 Double-base palindromes - Java 

 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
import java.util.ArrayList;
import java.util.Scanner;

public class Solution {

    private static ArrayList<Long> answer = new ArrayList<Long>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long k = scanner.nextLong();
        long sum = generateAnswer(n, k);
        System.out.println(sum);
        scanner.close();
    }

    private static long generateAnswer(long n, long k) {
        long sum = 0;
        for (long i = 1; i <= 9; i++) {
            String translated = Long.toString(i, (int) k);
            char[] chars = translated.toCharArray();
            int start = 0;
            int end = translated.length() - 1;
            boolean isPanlindrome = true;
            while (start < end) {
                if (chars[start++] != chars[end--]) {
                    isPanlindrome = false;
                    break;
                }
            }
            if (isPanlindrome) {
                System.out.println("i: " + i + " translated: " + translated);
                sum += i;
                answer.add(i);
            }
        }
        for (long i = 11; i <= n; i++) {
            String base10s = Long.toString(i);
            char[] base10 = base10s.toCharArray();
            int start = 0;
            int end = base10s.length() - 1;
            boolean isPanlindrome = true;
            while (start < end) {
                if (base10[start++] != base10[end--]) {
                    isPanlindrome = false;
                    break;
                }
            }
            if (!isPanlindrome) {
                continue;
            }
            String translated = Long.toString(i, (int) k);
            char[] chars = translated.toCharArray();
            start = 0;
            end = translated.length() - 1;
            isPanlindrome = true;
            while (start < end) {
                if (chars[start++] != chars[end--]) {
                    isPanlindrome = false;
                    break;
                }
            }
            if (isPanlindrome) {
                System.out.println("i: " + i + " translated: " + translated);
                sum += i;
                answer.add(i);
            }
        }
        return sum;
    }
}
Posted by at
Labels: ,

Project Euler #35 Circular primes - Java 

 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.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Solution {

    final private static Set<Long> answers = new HashSet<Long>();
    static {
        answers.add((long) 2);
        answers.add((long) 3);
        answers.add((long) 5);
        answers.add((long) 7);
    }

    public static void main(String[] args) {
        getAnswers();
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long sum = 0;
        for (Long l : answers) {
            if (l <= n) {
                sum += l;
            }
        }
        System.out.println(sum);
        scanner.close();
    }

    private static void getAnswers() {
        for (long i = 10; i <= 1000000; i++) {
            Set<Long> circles = getCircles(i);
            boolean test = true;
            if (circles == null) {
                continue;
            }
            for (Long l : circles) {
                if (!isPrime(l)) {
                    test = false;
                    break;
                }
            }
            if (test) {
                answers.addAll(circles);
            }
        }
    }

    private static Set<Long> getCircles(long l) {
        Set<Long> ret = new HashSet<Long>();
        ret.add(l);
        final int digitLength = (int) Math.log10(l) + 1;
        for (int i = 0; i < digitLength; i++) {
            int d = (int) (l % 10);
            if ((d & 1) != 1 || d == 5) {
                return null;
            }
            d *= Math.pow(10, digitLength - 1);
            l /= 10;
            l += d;
            ret.add(l);
        }
        return ret;
    }

    private static boolean isPrime(long i) {
        if (i == 2 || i == 3) {
            return true;
        }
        if ((i & 1) != 1) {
            return false;
        }
        for (long l = 3; l <= Math.sqrt(i); l += 2) {
            if (i % l == 0) {
                return false;
            }
        }
        return true;
    }
}
Posted by at
Labels: ,
Subscribe to: Posts (Atom)