求100以内的素数

什么是素数?

除0和1以外，只有1和它本身这两个因数的数是素数。如2，3，5，……

---

第一种方法：

  我们很容易找到1——10里面的素数：2，3，5，7。凡不是这4个数的倍数的数都为素数。

public class PrimeDemo {
    public static void main(String[] args){
        primeNumber();
    }

    public static void primeNumber(){
        int count = 4;
        StringBuilder sb = new StringBuilder();
        sb.append(2+" "+3+" "+5+" "+7+" ");
        for(int i=10;i<=100;i++){
            if(i%2==0||i%3==0||i%5==0||i%7==0){
                continue;
            }else {
                sb.append(i+" ");
                count++;
            }
        }
        System.out.println(count);
        System.out.println(sb.toString());
    }

}

第二种方法：

根据素数的定义：只有1和它本身这两个因数的数称为素数。可以理解为，一个数(n)，只要不能被[2，(n-1)]之间的数整除，那它就是一个素数。

以sqrt为分界点的原因：
  首先，因数是成对出现的。比如24,你找到个约数3,那么一定有个约数8,因为24/3=8。然后，这对约数必须一个在根号n之前，一个在根号n之后。因为都在根号n之前的话，乘积一定小于n（根号nX根号n=n）。同样，都在根号n之后的话，乘积一定大于n。所以，如果你在根号n之前都找不 到因数的话，那么根号n之后就不会有了。

public class PrimeNumber {
    public static void main(String[] args){
        //primeNumber();
        primeNumber2();
    }
    //根据素数的定义找素数
    public static void primeNumber(){
        int count = 0;
        int i;
        int j;
        for(i = 2;i<=100;i++){
            for(j = 2;j<=i-1;j++){
                if(i%j==0){
                    break;
                }
            }
            if(j>=i){
                count++;
                System.out.print(i+" ");
            }
        }
        System.out.println();
        System.out.println(count);
    }

    //============================优化====================================
    /*
     * 外层循环代表被除数。由于1既不是质数也不是合数，所以从2开始
     * 内层循环代表除数。
     * */
    public static void primeNumber2(){
        int count = 0;
        StringBuilder sb = new StringBuilder();
        for(int i=2;i<=100;i++){
            int j;
            int k = (int)Math.sqrt(i);
            for(j=2;j<=k;j++){
                if(i%j==0){
                    break;
                }
            }
            if(j>k){
                count++;
                sb.append(i+" ");
            }
        }
        System.out.println(count);
        System.out.println(sb.toString());
    }
}

第三种方法：

  除2以外的所有偶数都不是素数，因此可以筛选一半元素，剩下的数都为奇数。外层循环可筛选掉一半被除数。

  奇数 = 奇数 * 奇数，它不可能被一个偶数整除。内层循环可筛选掉一般除数。

public class PrimeNumber {
    public static void main(String[] args){
        isPrime();
    }


    public static void isPrime(){
        //2也为素数
        StringBuilder sb = new StringBuilder("2 ");
        int count = 1;//记录素数的个数。已经有2这个素数了，所以count的初始值为1
        for(int i = 3;i<=100;i+=2){//从3开始，以2为步长，限定每个被除数都是奇数
            int j;
            boolean flag = true;//flag为true时，是素数；为false时，是和数
            for(j=3;j<i;j+=2){//j从3开始，以2为步长，限定每个除数都是奇数。因为一个奇数是不可能被一个偶数整除的
                if(i%j==0){//如果i能够被j整除
                    flag = false;
                }
            }
            if(flag){
                count++;
                sb.append(i+" ");
            }
        }
        System.out.println(count);
        System.out.println(sb.toString());
    }
}

第四种方法(埃拉托斯特尼筛法)：

 具体步骤：

1. 先将1删去(因为1不是素数)。
2. 用2去除它后面的各个数，把能被2整除的数删掉，即把2的倍数删掉。
3. 用3去除它后面的各数，把3的倍数删掉。
4. 分别用5，7…各数作为除数去除这些数以后的各数。
5. 一直到sqrt(i)为止。然后重复上述步骤。

  上述操作需要一个很大的容器去装载所有数的集合，只要满足上述条件，即2的倍数大于1的全部置0，3的倍数大于1的全部置0，4的倍数大于1的全部置0……一直到这个数据集合的末尾，这样一来不为0的数就是素数了，然后按下标在里面进行查找。

public class PrimeNumber {
    public static void main(String[] args){
        isPrime();
    }
    public static void isPrime(){
        //默认值为0，0——素数；1——合数
        //这里写101是因为数组的下标是从0开始的，而要求的是1——100之间的素数
        int[] arr = new int[101];
        //0，1都不是素数，标记为1
        arr[0] = 1;
        arr[1] = 1;
        /*
        * 求1——100之间的素数，把2的倍数过滤掉，3的倍数过滤掉，5的倍数过滤掉，7的倍数过滤掉，一直到sqrt(100)的倍数过虑掉（这
        * 些都是2——sqrt(100)之间的素数的倍数）
        * */
        for(int i = 0;i<=Math.sqrt(100);i++){
            if(arr[i] == 0){
                //for(int j=2*i;j<=100;j+=i){
                //可以从2*i修改成i*i,因为在前面的循环中从2——(i-1)的倍数都已经验证过
                for(int j=i*i;j<=100;j+=i){
                    arr[j] = 1;
                }
            }
        }
        int count=0;
        for(int x = 0;x<=100;x++){
            if(arr[x]==0){
                count++;
                System.out.print(x+" ");
            }
        }
        System.out.println();
        System.out.println(count);
    }
}

欢迎大家给我建议，若诸位还有好的方法，欢迎一起交流。