【Java算法】求质数的算法

时间:2022-04-26 11:01:32

计算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个。