当前位置: 代码迷 >> 综合 >> Algorithm Gossip: Eratosthenes筛选求质数
  详细解决方案

Algorithm Gossip: Eratosthenes筛选求质数

热度:30   发布时间:2023-12-17 06:35:06.0
package main01;

import java.util.ArrayList;

public class CoreJava05 {

    /**
     * @param args

     * Algorithm Gossip: Eratosthenes筛选求质数 解题思路:

      过滤2的倍数,3的倍数,5的倍数,7的倍数.........N

     */

    public static void main(String[] args) {

        // TODO Auto-generated method stub

     //测试方法代码所用,

        System.out.println(Eratosthenes(30).toString());
    }

    public static ArrayList<Integer> Eratosthenes(int number) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int count = 0;
        int i = 0;
        int j = 0;
        int array[] = new int[number + 1];
        // 初始化数组不考虑1
        for (i = 2; i <= array.length - 1; i++) {
            array[i] = 1;
        }
        for (i = 2; i <= array.length - 1; i++) {
            // 从2开始凡是为2得倍数,3的倍数,4的倍数。。。。。。则将该值设为0
            for (j = i * i; j <= array.length - 1; j += i) {
                array[j] = 0;
            }
        }
        //将数组中为1的即为质数的下标保存在list集合中
        for (i = 2; i <= array.length - 1; i++) {
            if (array[i] == 1) {
                list.add(i);
            }
        }
        return list;
    }

}
  相关解决方案