计算100以内的质数

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

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

1 public class Zhishu { 2     public static void main(String[] args) { 3         int count= 0; 4         for(int n=2;n<=100;n++){ 5             boolean isTrue = true; 6             for(int t=n-1;t>1;t--){ 7                 if(n%t==0){ 8                     isTrue = false; 9                 }10             }11             if(isTrue==true){12                 count++;13                 System.out.println("this is a Zhishu "+n);14             }15         }16         System.out.println("count is "+count);17     }18 }

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

2.利用一个定理——如果一个数是合数，那么它的最小质因数肯定小于等于他的平方根。例如：50，最小质因数是2，2<50的开根号

再比如：15，最小质因数是3，3<15的开根号

　　合数是与质数相对应的自然数。一个大于1的自然数如果它不是合数，则它是质数。

　　上面的定理是说，如果一个数能被它的最小质因数整除的话，那它肯定是合数，即不是质数。所以判断一个数是否是质数，只需判断它是否能被小于它开跟后后的所有数整除，这样做的运算就会少了很多，因此效率也高了很多。

1 public class Zhishu { 2     public static void main(String[] args) { 3         int count= 0; 4         boolean isTrue = true; 5         for(int n = 2;n<=100;n++){ 6             for(int t = 2;t<=(int)Math.sqrt(n);t++){ 7                 if(n%t==0){ 8                     isTrue = false; 9                 }            10                 if(isTrue==true){11                     count++;12                     System.out.println("this is a Zhishu "+n);13                 }14             }15         System.out.println("count is "+count);16         }17     }18 }

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