java经典算法（一）求100以内的素数

亦凉 2022-06-12 10:30 177阅读 0赞

**一、用筛选法**

**所谓的筛选法**：是指从小到大筛去已知的一个素数的所有倍数，根据2我们可以筛去“4,6,8,...,100”等数，然后根据3可以筛去“9,15,...,99”等数，注意此时的6,12早就被作为2的倍数给筛去了，由于4已经被筛去了，所以下一个筛选数是5

**编程原理**：定义一个大小为101的数组,把被筛去的数赋值为1,留下未被筛去的并且数组下标大于等于2的数输出，输出的就是质数。

实例：

package rmd_lygp_front.test;
    
    public class Test {
    	
    	public static void main(String[] args) {
    		 int[] a = new int[101];  
    	        int i, j = 2;  
    	          
    	        while (j < 101) {  
    	            if (a[j] == 0) {  
    	                for (i = j + 1; i < 101; i++) {  
    	                    if (i % j == 0) {  
    	                        a[i] = 1;  
    	                    }  
    	                }  
    	            }  
    	            j++;  
    	        }  
    	          
    	        for (int k = 0; k < 101; k++) {  
    	            if (k >= 2 && a[k] == 0) {  
    	                System.out.println(k);  
    	            }  
    	        }  
    	}
    
    }

**二、普通方法：**

**证明：**使用k = (INT)Math.sqrt(i)来控制循环的可靠性，通过举例来证明当i=8时，他的值介于2的平方和3的平方之间，所以当4<i<9时,k=（INT）Math.sqrt(i) = 2； 3\*2< 8 < 3\*3 ,所以如果8能够被一个数整除的话就应该小于3大于1的整数， i=40的时候  40<7\*7  ,所以只要40不能被大于1小于等于7的数整除，就可以断定40不是质数

实例：

package rmd_lygp_front.test;
    
    public class Test {
    	
    	public static void main(String[] args) {
    		int i, j, k;  
            for (i = 2; i < 100; i++) {  
                k = (int) Math.sqrt(i);  
                for (j = 2; j <= k; j++) {  
      
                    if (i % j == 0)  
                        break;  
      
                }  
                if (j > k) {  
                    System.out.println(i + " ");  
                }  
            }  
    	}
    }