--/--/--

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

2007/11/04

幸運数

幸運数 - wikipedia

LuckyNumber.java

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

public class LuckyNumber {

    /**
     * 幸運数を求める.
     *
     * @param data 幸運数を求める自然数の数列
     * @return 幸運数の数列
     */
    public int[] sieve(int[] data) {
        //偶数を除く
        for (int i = 0; i < data.length; ++i) {
            if (data[i] % 2 == 0) {
                data[i] = -1;
            }
        }
        int[] target = new int[data.length + 1];
        data = pickupPositive(data);
        System.arraycopy(data, 0, target, 1, data.length);
        target[0] = -1; // 0番目は使わない
        target = sieve(target, 2);
        return pickupPositive(target);
    }

    /**
     * 幸運数を求める.
     *
     * @param data 幸運数を求める自然数の数列
     * @param index 除く位置の基数
     * @return 幸運数の数列
     */
    private int[] sieve(int[] data, int index) {
        if (data.length - 1 <= index) { // 0番目が余計なので-1
            return data;
        }
        int lucky = data[index];
        for (int n = 1; lucky * n < data.length; ++n) {
            data[lucky * n] = -1; // 削除マーキング
        }
        int[] tmp = pickupPositive(data);
        int[] next = new int[tmp.length + 1];
        System.arraycopy(tmp, 0, next, 1, tmp.length);
        next[0] = -1;
        return sieve(next, index + 1);
    }

    /**
     * 数列から自然数のみを取りだして返す.
     *
     * @param data 数列
     * @return data から取り出した自然数の数列
     */
    private int[] pickupPositive(int[] data) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < data.length; ++i) {
            if (data[i] > 0) {
                list.add(data[i]);
            }
        }
        Integer[] array = list.toArray(new Integer[list.size()]);
        int[] ret = new int[array.length];
        for (int i = 0; i < array.length; ++i) {
            //boxing
            ret[i] = array[i];
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] data = new int[100];
        for (int i = 1; i <= data.length; ++i) {
            data[i - 1] = i;
        }
        LuckyNumber calculater = new LuckyNumber();
        System.out.println(Arrays.toString(data));
        System.out.println(Arrays.toString(calculater.sieve(data)));
    }

}

巨大すぎワロタ。index から取り出すあたりをシンプルにしたくて 0 番目に -1 入れたりしてみたけどかえって複雑になったような。配列から自然数を取り出すところとかもっと簡単にできないのかなぁ。最初から配列に詰めるとしても配列の長さが適切に決められないし、list.toArray(new Integer[list.size()]);だと型が違うと怒られるし。あとで ArrayList 使ってやり直そう。

via: 幸運数 - みずぴー日記

スポンサーサイト

comment

post




上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。