用“埃氏筛法”求2～100以内的素数。

用“埃氏筛法”求2～100以内的素数。2～100以内的数，先去掉2的倍数，再去掉3的倍数，再去掉5的倍数，……依此类推，最后剩下的就是素数。

请上传压缩后的源代码文件，代码可直接并正确运行；

请注意代码风格：类名、变量名的命名，以及必要注释等等；

以防上传失败，请同时把代码贴到文本框中。

埃氏筛法定义：埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

步骤举例

详细列出算法如下：

列出2以后的所有序列：
- 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
标出序列中的第一个素数，也就是2，序列变成：
- 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
将剩下序列中，划掉2的倍数，序列变成：
- 2 3 5 7 9 11 13 15 17 19 21 23 25
如果现在这个序列中最大数小于最后一个标出的素数的平方，那么剩下的序列中所有的数都是素数，否则回到第二步。
本例中，因为25大于2的平方，我们返回第二步：
剩下的序列中第一个素数是3，将主序列中3的倍数划掉，主序列变成：
- 2 3 5 7 11 13 17 19 23 25
我们得到的素数有：2，3
25仍然大于3的平方，所以我们还要返回第二步：
现在序列中第一个素数是5，同样将序列中5的倍数划掉，主序列成了：
- 2 3 5 7 11 13 17 19 23
我们得到的素数有：2，3，5 。
因为23小于5的平方，跳出循环.

结论：2到25之间的素数是：2 3 5 7 11 13 17 19 23。

题目实现

package 埃氏筛法求素数;

public class Main {

	public static void main(String[] args) {
		int aa[]=new int [101];
		aa[0] = aa[1] = 1;
        aa[2]=0;
        int k=2,tt=0;
        while(tt<101)
            {
                for(int i=1; i<; i++) //将不是素数的数筛出
                {
                	if(i%k==0&&i!=k) 
                		aa[i]=1;//不符合要求的全部置为1
                }
                    
                for(int i=1; i<; i++) //将筛选后的第一个数当做新的筛子
                {
                	if(i>k&&aa[i]==0)
                    {
                        k=i;
                        break;
                    }
                }
                tt++;
            }

        for(int i=1; i<; i++)
            if(aa[i]==0) ("%d ",i);
	}

}

还有一种方法也可以

/*需求：用埃氏筛法求解100(扩展到n)以内的素数；
 *思路：
 *1. 设定一个边界(由用户输入)，用以求1到它之内的素数； 
 *2. 明确素数、埃氏筛法的概念；
 *3. 需要用到数组来储存素数的标记；
 *4. 埃氏筛法中，只需要从这个数的当前倍数判断即可，如5的5倍、5的6倍，因为5的2、3、4倍已经分别在2、3、4的5倍体现；
 *5. 每行输出10个素数，并求出总个数；
 *步骤：
 *1. 引入Scanner，并引导用户输入一个正整数n来当做边界；
 *2. 如果数据不能被所有2到n的平方根整除，那么这个数就是一个素数；(埃氏筛法核心思想1)；
 *3. 默认给定区间除0、1外全部为素数，引入int i、j，在区间内(即应不大于给定的n)从j的j倍开始遍历，如果有数值不满足素数条件则判为true，即实现了对全部数据的标记；(埃氏筛法核心思想2)；
 *4. 用一个布尔数组来存储标记(true、false)，并计算true的个数；
 *5. 设计输出语句，囊括区间、素数个数,并做到每行打印10个素数。
 */
import .*;
public class Week3Homework 
{
    public static void main(String[] args) 
    {
        ("请输入一个正整数用以求解0到它的素数：");
        Scanner intnum = new Scanner();
        int n = ();
        isPrime(n);//调用isPrime函数
    }
public static void isPrime(int num)//定义isPrime，对数据做标记
    {
        boolean[] mark = new boolean[num+1];//因为角标从0开始，为了对应，数据从0开始，所以长度为num+1
        mark[0] = false;//0不是素数
        mark[1] = false;//1不是素数
        for(int i = 2; i <= num; i++)
            {
                mark[i] = true;//初始化：假定2到num都是素数，均标识为true
            }
        for(int i = 2; i <= (num);i++)//埃氏筛法核心思想的体现
        {
            if(mark[i] == true)
            {
                for(int j = i;j*i<=num;j++)//更换标记，剔除非素数
                {
                    mark[j*i] = false;//i的倍数全部置为false
                }
            }
        }
        int count = 0;
        ("0到"+num+"的素数是：");
        for(int i = 2; i<=num; i++)//对布尔数组进行遍历，计算true标记的个数(即素数的个数)
        {
            if(mark[i] == true)
            {
                count++;
                (i+"\t");//"\t"是横向制表符
                if(count%10 == 0)//一行输出10个数据后，换行
                {
                    ();
                }
            }
        }
        ("\n0到"+num+"中的素数一共有"+count+"个。");
    }
}

秒客网

用“埃氏筛法”求2～100以内的素数。

步骤举例

相关文章