两种求素数

判断素数的两种方法：

第一种就是直接遍历2到sqrt(n)找是否有可以整除的数字

第二种是筛法：

用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。如有：

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

1不是素数，去掉。剩下的数中2最小，是素数，去掉2的倍数，余下的数是：

3 5 7 9 11 13 15 17 19 21 23 25 27 29

剩下的数中3最小，是素数，去掉3的倍数，如此下去直到所有的数都被筛完，求出的素数为：

2 3 5 7 11 13 17 19 23 29

用筛法求素数效率更高。

import java.util.Scanner;

/*
 *判断素数的两种方法：
 *1、一般求素数算法
 *2、筛法求素数
 */

public class Main {
    
    static boolean[] isPrime=new boolean[100000];

    public static void main(String[] args) {
        
//        System.out.println(yiBan(8));
        
        shaiFa();    //筛法求数数
        
        Scanner scanner=new Scanner(System.in);
        while(true){
            int n=scanner.nextInt();
            System.out.println(isPrime[n]);
        }
    }  
    
    static boolean yiBan(int num){        //一般法求素数
        if(num<=1){
            return false;
        }
        for(int i=2;i<=Math.sqrt(num);i++){
            if(num%i==0){
                return  false;
            }
        }
        return true;
    }
    
    static void shaiFa(){        //筛法求素数
        for(int i=0;i<isPrime.length;i++){
            isPrime[i]=true;
        }
        isPrime[0]=isPrime[1]=false;
        for(int i=2;i<isPrime.length;i++){
            if(isPrime[i]){
                for(int j=2*i;j<isPrime.length;j+=i){
                    isPrime[j]=false;
                }            
            }
        }
    }

}