埃氏筛法求素数 java 代码

Posted by 撒得一地 on 2016年4月20日 in 杂谈

埃氏筛法求素数,下面是完整的java代码:

import java.util.Scanner;

/**
 * Author:  HF
 * Blog:    blog.nicerData.com | Email: androidiosgood@gmail.com
 * Date:    2014/5/4
 * Description:  埃氏筛法求素数
 */
public class FilterPrime {

    public static void main(String[] args) {
        System.out.println("Enter an integer number:");
        Scanner input = new Scanner(System.in);
        int number = input.nextInt();
        Prime(number);
    }//main

    //利用埃氏筛法进行筛选的过程
    public static void Prime(int number) {

        //假设一个数组,每个数组元素代表的是一个标记(Y/N)
        char[] arr = new char[number + 1];
        //标记Y表明是素数,N表明不是素数,初始化假设全为素数,都先标记为Y
        for (int i = 0; i < arr.length; i++) {
            arr[i] = 'Y';
        }

        for (int i = 2; i <= number; i++) {
            if (arr[i] == 'Y') {
                //i的初始值为2,j代表倍数,根据埃氏筛法:凡是i的j倍的数都为'N',表示筛除出来的非素数
                for (int j = i; j * i <= number; j++) {
                    arr[i * j] = 'N';
                }
            }//if
        }//for

        //打印结果
        for (int i = 2; i <= number; i++) {
            if (arr[i] == 'Y') {
                System.out.print(i + " ");
            }
        }//for
    }//Prime
}

上一篇:

下一篇:

相关推荐

网站地图|XML地图

Copyright © 2015-2024 技术拉近你我! All rights reserved.
闽ICP备15015576号-1 版权所有©psz.