Java中求多少以内的质数？

待我称王封你为后i 2022-05-22 10:56 196阅读 0赞

下午研究了一波100以内的质数求法，大致的思路就是从1到这个数全部除一遍，双重for循环，的确可以做到

但是效率却不尽如人意，于是自己稍微变通了一下，下面是代码：

// 质数
    	public static Set<Integer> Test1(int i) {
    		Set<Integer> set = new HashSet<Integer>();
    		for (int x = 2; x <= i; x++) {
    			set.add(x);
    		}
    		for (; i > 1; i--) {
    			for (int j = 2; j < i; j++) {
    				if (i % j == 0) {
    					set.remove(i);
    					break;
    				}
    			}
    		}
    		return set;
    	}

还有一个是在网上找的一个，暂定为方法2：

public static void Test2(int x) {
    
    		int j;
    		for (int i = 2; i <= x; i++) // 1不是素数，所以直接从2开始循环
    		{
    			j = 2;
    			while (i % j != 0) {
    				j++; // 测试2至i的数字是否能被i整除，如不能就自加
    			}
    			if (j == i) // 当有被整除的数字时，判断它是不是自身
    			{
    				System.out.println(i); // 如果是就打印出数字
    			}
    		}
    
    	}

于是对比一下两者的计算效率：

<table> 
 <tbody> 
  <tr> 
   <td>单位&nbsp; &nbsp; &nbsp;秒/s</td> 
   <td>1K以内质数</td> 
   <td>1w以内质数</td> 
   <td>10w以内质数</td> 
   <td>100w以内质数</td> 
  </tr> 
  <tr> 
   <td>test1</td> 
   <td>0.002&nbsp;&nbsp;&nbsp;&nbsp;</td> 
   <td>0.032</td> 
   <td>1.974</td> 
   <td>154.142</td> 
  </tr> 
  <tr> 
   <td>test2</td> 
   <td>0.003</td> 
   <td>0.039</td> 
   <td>1.682</td> 
   <td>131.428</td> 
  </tr> 
 </tbody> 
</table>

在2.3w时两者的效率相同，小于2.3w时 方法1效率更高，更大则方法2胜出。

但是在百万级别的时候，都是很慢，于是找到一个新的思路，更改了一下方法1的代码：

// 质数
    	public static Set<Integer> Test1(int i) {
    		Set<Integer> set = new HashSet<Integer>();
    		for (int x = 2; x <= i; x++) {
    			set.add(x);
    		}
    		for (; i > 1; i--) {
    			int temp = (int) Math.sqrt(i);//对i进行了开方
    			for (int j = 2; j <= temp; j++) {
    				if (i % j == 0) {
    					set.remove(i);
    					break;
    				}
    			}
    		}
    		return set;
    	}

直接贴出来改进后的100w以内质数的计算时间：

![70][]                        运算速度提升了100倍！

不过这并不是最优解，贴出大神的方法：

public static void Test3(int x) {
    		for (int i = 2; i <= x; i++) {
    			int temp = (int) Math.sqrt(i);
    			// 我把那个aqrt单独提出来,这样速度稍微快一点,虽然在100内变化不大,但如果是10000000内的素数呢?
    			if (i <= 3) {
    				System.out.println(i + " is a prime");
    			} else {
    				for (int j = 2; j <= temp; j++) {// 把Math.sqrt(i)转换为int类形
    					if (i % j == 0) {
    						break;
    					}
    					if (j >= temp) {
    						System.out.println(i + " is a prime");
    					}
    				}
    
    			}
    		}
    	}

100w以内质数运算时间如下：

![70 1][]

看到开方真是茅塞顿开！

下面是大神方法的地址：[点击打开链接][Link 1]

[70]: /images/20220522/415e62b0ddfc43dc9bc9d1574f0ddaa2.png
[70 1]: /images/20220522/0a0a9587e26c4fc785586eb80aa1ff19.png
[Link 1]: https://blog.csdn.net/zeb_perfect/article/details/43459471