java中找素数的个人心得

找素数是一项基本技能，方法也很多。在此，小编根据自己的经验，总结一下我所知道的找素数的方法。

在此，我以找50以内的素数为例。

方法一

package sweet;

public class detached
{
    public static void main(String[] args)
    {
    
     //檬檬自己写的普通方法求素数代码
          int k = 0;
        System.out.println("50以内的素数分别为：");
        for (int i = 2; i <= 50; i++)
        {

            for (int j = 2; j <= 25; j++)
            {
                if (i % j == 0)
                {
                    if (j < i)
                        break;
                    if (j == i)
                        System.out.print(i + " ");
                    break;
                }

                if (i % j != 0)
                {
                    if (j == 25)
                        System.out.print(i + " ");
                }

            }

        }

}
}

分析：

已知1既不是素数，又不是合数，所以我们对50以内的数的判断就只需要从2开始（有人会说，其实50以内的素数我都能背出来了，好像答案都很已知啊。檬檬只能说，这个时候我们不能钻这种牛角尖，我们要试图掌握一种通法）利用一个for循环，我们可以对每一个数进行判断。最关键的也就是第二个for循环里面的内容了，它告诉我们如何对每一个数字进行素合数的判断。

看第二个for循环的关键要素，第一个部分j = 2和第二个部分j <=25 。

有朋友就有疑问了，为什么j不能从0或1开始呢？我来为大家一一解答。首先，j不能等于0其实是很明显的，看看我们后面的代码，你会发现我们的j有什么身份，它是一个除数，在小学我们就知道，一个除数它是不能等于0的。那么，为什么j不能等于1呢？让我们用反证法来说明。假设j从1开始，则对于外层循环中的任何一个数，它一进入内层for循环，就会执行break语句跳出内层循环。其最终的结果是，两层循环下来，程序什么有意义的事情都没有做。

那么，我们的j为什么要小于等于25呢？25有什么特别的含义吗？当然有了，它是我们外层循环中循环变量上限值50的1/2。这个关系可就把两个循环联系在一起了。可是这样做的意义究竟是什么呢？这样做其实是为了简化循环。且听我分析：一个合数，它除了可以写成1和它本身的乘积之外，它还可以写成另外两个因数的乘积，而这另外两个因数必定满足：其中一个因数的值>=这个数的一半，另一个因数的值<=这个数的一半，所以，对于一个给定的数字，如果在这个数字的1/2以内的整数中，除了1以外没有一个可以整除它，那个这个数就已经可以确定是一个素数了，而不再需要看它的后1/2的情况。举个例子，已知17是一个素数，它的一半是8.5，那么小于等于8.5的所有整数分别是1、2、3、4、5、6、7、8，我们会发现，除了1以外没有一个数可以整除17，根据我们上面的说法，这个时候就可以确定17是一个素数了，而不再需要看大于等于8.5的整数是否能整除17，而事实也确实如此，在大于等关于8.5的所有整数9、10、11、12、13、14、15、16、17中只有17可以整除17，而这个结果也符合17是个素数的结论。所以，我们只需要判断到50的一半25就可以了。

在这个算法中，这种思想体现得并不是很淋漓尽致，只有在判断50是否为素数的时候才严格用到这种思想，但在下一种算法中就体现得很深刻了。

回到我们的代码，在第二个for循环中，我用了两个大的if语句来分类判断，当j可以整除i时，我们不能通过i有因数而直接否定它是素数，我们应该先判断这个因数的值，如果这个因数是它本身的话，那么我们就说它也是素数（在i%j ==0这种情况下，i如果是素数的话，则这个因数j要么是1，要么是它本身，而我们已经证明这个因数不能为1，所以我们说在这种情况下，i是素数的充要条件就是i等于j），运用类似的辩证思维，如果j不能整除i，我们也不能立刻就说明i为素数，只有当j等于最后一个数25时，还是不能整除i，那么我们可以说明i真的是一个素数了。

这个算法的思路我自认为是很巧妙的，其中的反证、辩证思维体现得很充分，我觉得朋友们要是感兴趣的话可以反复体会体会。

方法二

package sweet;

public class detached
{
    public static void main(String[] args)
    {

             //小布老师给的求素数代码
             int m, n;// 变量n为要判断的数字
        
            System.out.println("50以内的素数有：");
            A: for (n = 2; n <= 50; n++) {
            for (m = 2; m <= n / 2; m++) {
            if (n % m == 0)
            continue A;
            // 如果能被整除则变量n肯定不是素数，跳出内层循环
            }
            System.out.print(n + " " );//输出素数
            }

}
}

这个代码是我的老师给出的一个代码，看起来更加地简洁，也更加地实用。

它就非常充分地体现了我们上面谈到的简化循环的思想，关键语句m <=n/2，两个循环之间建立起联系。

素数2和3通过不进入内层循环的方式判断出来，而其他的素数通过在它的数值前一半的所有整数中找不到它的因数来判断。

方法三

package sweet;

public class detached
{
    public static void main(String[] args)
    {


        //檬檬自己写的厄拉多塞筛选法求素数代码

       //此处仍然是以求50以内的素数，所以我构造了一个“筛集”数组a，里面的数分别是从2到50的整数
        int []a = new int[49];
        for(int i0 = 0;i0<49;i0++)
        {
            
            a[i0]=i0+2;
        }
        
        int m = 2;
        int t  = 0;                                      //m和t是两个全局变量，t用于为“素数集”添加元素，m用于得到每一轮循环后产生的新素数
        int []sushumen = new int [49];                //我把表示“素数集”的数组的大小定义得和表示“筛集”的数组的大小一样大，因为我的素数个数未知，而这是最相关最保险的一种定义方式
        
        
        
        for(int p = 0;p<49;p++)
        {
            sushumen[t++] = m ;
            a = delete(a,m);
            m = number(a);

         if(m==0)break;         //这一个判断语句很关键。我们这里循环了49轮来找素数，是假设所判断的49个数全部都是素数，事实上，素数的个数肯定是少于我们所判断的个数的，所以依照我们这种赋0的方法，在某一轮结束之后，这个筛集中的数全部都是0，这个时候也恰恰可以作为循环结束的标志。
        }
        sushumen[t++] = m;

       //简单的打印输出
        System.out.println("50以内的素数分别为：");
        for(int p = 0;p<49;p++)   
        {
            if(sushumen[p]!=0)
            System.out.print(sushumen[p]+" ");
        }
    }

//函数number用于寻找到一个数组中第一个不为零的数，并返回（用于在筛集中删除了某个数的倍数以后，找到产生的新素数。前提：在筛集中对某个数的倍数进行删除时，并不是实实在在地把它从数组中删除掉，而是将那个元素赋为0【这一点是可以改进的：如果哪位朋友知道了如何可放缩地删除数组元素，就可以简化这个步骤】）
    public static int number(int a[])
    {
        int b1 = 0;
        for(int b = 0;b<a.length;b++)
        {
            if(a[b]!=0) { b1 = a[b];break;}
        }
        return b1;
    }

//函数delete就是用来对一个数组删除指定数m的倍数，实际上是将这个数的倍数所在的变量赋为0，然后返回这个数组
    public static int[] delete(int a[],int m)
    {
        for(int i = 0;i<a.length;i++)
        {
            if(a[i]%m==0)a[i] = 0;
            
        }
        return a;
    }

}
}

这个代码是我在只看了厄拉多塞筛选法的算法解析后，根据自己的理解打出来的，因为我想对比一下自己的代码和教材中给出的代码。结果是基于相同的思想，我们的具体实现过程也挺不同的，这种不同是真的有趣。

知识普及：厄拉多塞筛选法求素数

厄拉多塞是古希腊的一名科学家。且n以内的素数的思想是，首先将2~n的数放入一个集合（筛集），将已知的最小素数2放入素数集，再去掉筛集中所有2的倍数后，筛集中的最小值3即为新找到的素数，再去掉筛集中所有3的倍数，筛集中的最小数5即为新找到的素数。依法执行下去，直到筛集为空时，素数集中得到数就是我们要找的全部素数。

方法四

package sweet;

public class detached
{
    public static void main(String[] args)
    {

//教材上的原版厄拉多塞筛选法代码

int maxNumber = 50;//命令行参数，获取素数的范围(教材int maxNumber = Integer.parseInt(args[0]);)
        int arraySize = maxNumber/3;//素数集的大小
        int primeNo[] = new int [arraySize];//素数集合
        int index,num,i,primeCount;
        primeNo[0] = 2;     //把第一个素数放入素数集合
        primeCount = 1;     //素数的个数
        index = 1;//下一个素数存放的位置
        num = 3;//测试数，从奇数开始测试，偶数不需要测试
        
        
        do
        {
            i = 0;   //素数集合上的循环变量
            while(i<primeCount && (num % primeNo[i]!=0))//用素数集合中的数测试num
                i++;
            if(i==primeCount)    //num是素数
            {
                primeNo[index] = num;   //把num放入到素数集中
                index++;                 //下标递增
                primeCount++;            //素数个数增加
            }
            num+=2;                      //测试下一个数
        
        }while(num<maxNumber);
        
        //打印输出
        System.out.println("50以内的素数：");
        for(i = 0;i<primeCount;i++)
        {
            System.out.print(" "+primeNo[i]);
            if((i+1)%10==0)   System.out.println();
                
        }
                System.out.println();
                System.out.println("素数个数："+primeCount);
    }
}

方法四的优点：1、它进一步简化了循环，因为它只测试了奇数2、它设计了一个控制格式的语句