JavaでProject Euler Problem 1〜10

今さらJavaをおぼえなければいけないみたいなので、とりあえず10問解いてみた。

Problem 1

C++とほぼ同じ。

public class e001 {
    public static void main(String args[]) {
        int     s = 0;
        int     N = 1000;
        for(int n = 1; n < N; ++n) {
            if(n % 3 == 0 || n % 5 == 0)
                s += n;
        }
        System.out.println(s);
    }
}

Problem 2

Fibonacci数列の生成と偶数の分離と和を取る部分が切り離せない。すなわちコードの再利用ができない。

public class e002 {
    public static void main(String args[]) {
        int     s = 0;
        int     N = 4000000;
        int     a = 1;
        int     b = 1;
        while(a <= N) {
            if(a % 2 == 0)
                s += a;
            int tmp = b;
            b += a;
            a = tmp;
        }
        System.out.println(s);
    }
}

Problem 3

デフォルト引数は使えない。

public class e003 {
    static long max_factor(long n) {
        return max_factor(n, 2);
    }
    
    static long max_factor(long n, long p0) {
        for(long p = p0; p * p <= n; ++p) {
            if(n % p == 0)
                return max_factor(n / p, p);
        }
        return n;
    }
    
    public static void main(String args[]) {
        long    N = 600851475143L;
        System.out.println(max_factor(N));
    }
}

Problem 4

とにかく長い。タプルがあれば短くなるのに。ComparatorはなぜGenericが使えないのか。Genericの意味もよくわかっていないが。

public class cMul {
    int     m;
    int     n;
    int     p;  // m * n
    
    cMul(int a, int b) {
        m = a;
        n = b;
        p = a * b;
    }
    
    int get_m() { return m; }
    int get_n() { return n; }
    int get_p() { return p; }
}

import java.util.Comparator;

public class MulComparator implements Comparator {
    public int compare(Object o1, Object o2) {
        cMul    m1 = (cMul)o1;
        cMul    m2 = (cMul)o2;
        if(m1.get_p() < m2.get_p())
            return 1;
        else if(m1.get_p() > m2.get_p())
            return -1;
        else
            return 0;
    }
}

import java.util.PriorityQueue;

public class e004 {
    static int reverse(int n) {
        int     s = 0;
        while(n > 0) {
            s = s * 10 + n % 10;
            n /= 10;
        }
        return s;
    }
    
    static boolean is_palindromic(int n) {
        return reverse(n) == n;
    }
    
    static int get_max_palindromic(int N) {
        PriorityQueue<cMul> pq = new PriorityQueue<cMul>(1, new MulComparator());
        pq.add(new cMul(N - 1, N - 1));
        while(pq.size() > 0) {
            cMul    a = pq.poll();
            if(is_palindromic(a.get_p()))
                return a.get_p();
            if(a.get_m() == a.get_n())
                pq.add(new cMul(a.get_m() - 1, a.get_m() - 1));
            pq.add(new cMul(a.get_m(), a.get_n() - 1));
        }
        return 0;
    }
    
    public static void main(String args[]) {
        final int   N = 1000;
        System.out.println(get_max_palindromic(N));
    }
}

Problem 5

public class e005 {
    static int gcd(int n, int m) {
        return m == 0 ? n : gcd(m, n % m);
    }
    
    static int lcm(int n, int m) {
        return n / gcd(n, m) * m;
    }
    
    public static void main(String args[]) {
        final int   N = 20;
        int     s = 1;
        for(int n = 1; n <= N; ++n)
            s = lcm(s, n);
        System.out.println(s);
    }
}

Problem 6

public class e006 {
    public static void main(String args[]) {
        final int   N = 100;
        int     s1 = 0;
        for(int n = 1; n <= N; ++n)
            s1 += n;
        int     s2 = 0;
        for(int n = 1; n <= N; ++n)
            s2 += n * n;
        System.out.println(s1 * s1 - s2);
    }
}

Problem 7

エラトステネスのふるい。素数定理使って手抜き。

import java.util.ArrayList;

public class e007 {
    static ArrayList make_primes(int N) {
        boolean[]   a = new boolean[N+1];
        for(int k = 2; k <= N; ++k)
            a[k] = true;
        for(int p = 2; p * p <= N; ++p) {
            for(int k = p * p; k <= N; k += p)
                a[k] = false;
        }
        ArrayList   b = new ArrayList();
        for(int k = 2; k <= N; ++k) {
            if(a[k])
                b.add(k);
        }
        return b;
    }
    
    public static void main(String args[]) {
        final int   N = 10001;
        final int   M = (int)(N * Math.log((double)N) * 2);
        final ArrayList primes = make_primes(M);
        System.out.println(primes.get(N-1));
    }
}

Problem 8

import java.util.ArrayList;

public class e008 {
    public static void main(String args[]) {
        final String    s =
                "73167176531330624919225119674426574742355349194934" +
                "96983520312774506326239578318016984801869478851843" +
                "85861560789112949495459501737958331952853208805511" +
                "12540698747158523863050715693290963295227443043557" +
                "66896648950445244523161731856403098711121722383113" +
                "62229893423380308135336276614282806444486645238749" +
                "30358907296290491560440772390713810515859307960866" +
                "70172427121883998797908792274921901699720888093776" +
                "65727333001053367881220235421809751254540594752243" +
                "52584907711670556013604839586446706324415722155397" +
                "53697817977846174064955149290862569321978468622482" +
                "83972241375657056057490261407972968652414535100474" +
                "82166370484403199890008895243450658541227588666881" +
                "16427171479924442928230863465674813919123162824586" +
                "17866458359124566529476545682848912883142607690042" +
                "24219022671055626321111109370544217506941658960408" +
                "07198403850962455444362981230987879927244284909188" +
                "84580156166097919133875499200524063689912560717606" +
                "05886116467109405077541002256983155200055935729725" +
                "71636269561882670428252483600823257530420752963450";
        
        final int   N = s.length();
        int max = 0;
        int a[] = new int[N];
        for(int k = 0; k < N; ++k)
            a[k] = Integer.parseInt(s.substring(k, k + 1));
        for(int k = 0; k < N - 4; ++k) {
            int     m = 1;
            for(int l = k; l < k + 5; ++l)
                m *= a[l];
            max = Math.max(max, m);
        }
        
        System.out.println(max);
    }
}

Problem 9

素因数分解から約数を生成。
ものすごく書きにくい。

import java.util.ArrayList;

public class e009 {
    static ArrayList factorize(int n) {
        ArrayList   fs = new ArrayList();
        for(int p = 2; p * p <= n; ++p) {
            if(n % p == 0) {
                int e = 1;
                n /= p;
                while(n % p == 0) {
                    ++e;
                    n /= p;
                }
                fs.add(new Fact(p, e));
            }
        }
        if(n > 1)
            fs.add(new Fact(n, 1));
        
        return fs;
    }
    
    static int pow(int p, int e) {
        return e == 0 ? 1 : p * pow(p, e - 1);
    }
    
    static int value_f(ArrayList fs) {
        int     n = 1;
        for(Object o : fs) {
            Fact    f = (Fact)o;
            n *= pow(f.get_p(), f.get_e());
        }
        return n;
    }
    
    static ArrayList tail(ArrayList a) {
        ArrayList   b = new ArrayList(a.size() - 1);
        for(int k = 1; k < a.size(); ++k) {
            b.add(a.get(k));
        }
        return b;
    }
    
    static ArrayList cons(Fact f, ArrayList a) {
        ArrayList   b = new ArrayList();
        b.add(f);
        for(Object o : a)
            b.add((Fact)o);
        return b;
    }
    
    static ArrayList sub_f(ArrayList a, ArrayList b) {
        if(b.size() == 0)
            return a;
        
        ArrayList   c = new ArrayList();
        int     l = 0;
        for(int k = 0; k < a.size(); ++k) {
            final   Fact    f1 = (Fact)a.get(k);
            final   Fact    f2 = (Fact)b.get(Math.min(l, b.size() - 1));
            if(f1.get_p() == f2.get_p()) {
                if(f1.get_e() > f2.get_e())
                    c.add(new Fact(f1.get_p(), f1.get_e() - f2.get_e()));
                ++l;
            }
            else {
                c.add(f1);
            }
        }
        return c;
    }
    
    static ArrayList divides(ArrayList fs) {
        if(fs.size() <= 0) {
            ArrayList   divs = new ArrayList();
            divs.add(new ArrayList());
            return divs;
        }
        else {
            ArrayList   divs = new ArrayList();
            Fact    f = (Fact)fs.get(0);
            final int   p = f.get_p();
            final int   e = f.get_e();
            for(Object o : divides(tail(fs))) {
                ArrayList   div = (ArrayList)o;
                divs.add(div);
                for(int e1 = 1; e1 <= e; ++e1) {
                    divs.add(cons(new Fact(p, e1), div));
                }
            }
            return divs;
        }
    }
    
    static int gcd(int n, int m) {
        return m == 0 ? n : gcd(m, n % m);
    }
    
    static boolean is_right_triangle(int n1, int n2, int n3) {
        return n3 % 2 == 1 && n2 < n3 && n3 < n2 * 2 && gcd(n2, n3) == 1;
    }
    
    public static void main(String args[]) {
        final int   N = 1000;
        ArrayList   fs = factorize(N / 2);
        ArrayList   divs = divides(fs);
        for(Object o : divs) {
            ArrayList   fs1 = (ArrayList)o;
            ArrayList   fs2 = sub_f(fs, fs1);
            final int   n1 = value_f(fs1);
            ArrayList   divs2 = divides(fs2);
            for(Object o2 : divs2) {
                ArrayList   fs3 = (ArrayList)o2;
                ArrayList   fs4 = sub_f(fs2, fs3);
                final int   n2 = value_f(fs3);
                final int   n3 = value_f(fs4);
                if(is_right_triangle(n1, n2, n3)) {
                    final int   l = n1;
                    final int   m = n2;
                    final int   n = n3 - n2;
                    final int   a = l * (m * m - n * n);
                    final int   b = 2 * l * m * n;
                    final int   c = l * (m * m + n * n);
                    System.out.println(a * b * c);
                }
            }
        }
    }
}

Problem 10

Generic版のListを使ってエラトステネスのふるい。

import java.util.ArrayList;
import java.util.List;

public class e010 {
    static List<Integer> make_primes(int N) {
        boolean[]   a = new boolean[N+1];
        for(int k = 2; k <= N; ++k)
            a[k] = true;
        for(int p = 2; p * p <= N; ++p) {
            for(int k = p * p; k <= N; k += p)
                a[k] = false;
        }
        List<Integer>   b = new ArrayList<Integer>();
        for(int k = 2; k <= N; ++k) {
            if(a[k])
                b.add(k);
        }
        return b;
    }
    
    static long sum(List<Integer> a) {
        long    s = 0;
        for(int k = 0; k < a.size(); ++k)
            s += a.get(k);
        return s;
    }
    
    public static void main(String args[]) {
        final int   N = 2000000;
        final List<Integer> primes = make_primes(N);
        System.out.println(sum(primes));
    }
}