【Java算法】求质数的算法

计算100以内的质数

1.质数：大于1的整数中，只能被自己和1整除的数为质数。

   如果这个数，对比自己小1至2之间的数字，进行求余运算，结果都不等于0，则可以判断该数为质数。

public class Zhishu {
    public static void main(String[] args) {
        int count= 0;
        for(int n=2;n<=100;n++){
            boolean isTrue = true;
            for(int t=n-1;t>1;t--){
                if(n%t==0){
                    isTrue = false;
                }
            }
            if(isTrue==true){
                count++;
                System.out.println("this is a Zhishu "+n);
            }
        }
        System.out.println("count is "+count);
    }
}

运行结果显示所有质数，共25个。

2.利用一个定理——如果一个数是合数，那么它的最小质因数肯定小于等于他的平方根。例如：50，最小质因数是2，2<50的开根号
再比如：15，最小质因数是3，3<15的开根号
　　合数是与质数相对应的自然数。一个大于1的自然数如果它不是合数，则它是质数。
　　上面的定理是说，如果一个数能被它的最小质因数整除的话，那它肯定是合数，即不是质数。所以判断一个数是否是质数，只需判断它是否能被小于它开跟后后的所有数整除，这样做的运算就会少了很多，因此效率也高了很多。

public class Zhishu {
    public static void main(String[] args) {
        int count= 0;
        boolean isTrue = true;
        for(int n = 2;n<=100;n++){
            for(int t = 2;t<=(int)Math.sqrt(n);t++){
                if(n%t==0){
                    isTrue = false;
                }            
                if(isTrue==true){
                    count++;
                    System.out.println("this is a Zhishu "+n);
                }
            }
        System.out.println("count is "+count);
        }
    }
}

运行结果显示所有质数，共25个。