【经典面试题二】统计素数个数的两种解决方法

本是古典何须时尚 2022-09-12 01:00 144阅读 0赞

## 题目：统计n以内的素数个数 ##

> 素数：只能被1和它自身整除的自然数，0、1除外  
> 例：  
> 输入：100  
> 输出：25

#### 解法一：暴力法（简单直接） ####

通过循环来判断每一个数是否为素数。  
因为这个方法简单直接，所以直接贴代码（后面有方法优化）

//暴力法
    public static int Bf(int n){
        
        int count = 0;
        for(int i = 2; i < n; i++){
        
            count += isPrime(i) ? 1:0;//使用三目运算判断是否为素数，是+1，否+0
         }
        return count;
    }
    //判断该数是否为素数
    private static boolean isPrime(int i) {
        
        for(int j = 2;j < i;j ++){
        
            if(i % j == 0){
        
                return false;
            }
        }
        return true;
    }

这是大家都能想到的实现，虽然这是暴力解法，但是也有可优化的地方  
例如数字12，会出现下面几种乘法

> 2 \* 6 = 12  
> 3 \* 4 = 12  
> 4 \* 3 = 12  
> 6 \* 2 = 12

很显然要判断是否是素数，只需执行这个数的一半循环就行，所以判断是否为素数的方法就可以优化为以下：

//判断该数是否为素数
    private static boolean isPrime(int i) {
        
    	//j*j <= i 即等于j < 根号i
        for(int j = 2;j * j <= i;j ++){
        
            if(i % j == 0){
        
               return false;
            }
        }
        return true;
    }

面试过程中如果出现这道题，你只以上面那一种方法解答的话，很明显达不到面试官所要的要求，毕竟暴力解法大家都知道的。

所以上第二种解法：

### 解法2：埃式筛选法 ###

这是一名为Eratosthenes的人发明的，其原理：

把数据分为素数与非素数（合数），利用合数（非素数）的概念：素数 \* n 必然是合数。  
例：

> 素数：2  
> 则：2 \* 2 = 4，2 \* 3 = 6，2 \* 4 = 8…这些积数就肯定不是素数  
> 因此将他们标记为true(非素数)

这个算法与上面的有什么不同呢？  
1、定义boolean数组来标记每一个数是否为素数（false表示素数）  
2、找到一个素数即将与此素数作为因子的合数标记为true，无需每个数都遍历一遍

代码实现如下：

//埃筛法
    public static int asf(int n){
        
       //定义素数bool数组，默认false是素数
       boolean[] isPrime = new boolean[n];
       int count = 0;
       for (int i = 2;i < n;i ++){
        
           if(!isPrime[i]){
        //判断i位置是否为false
              count ++;
               /**
               * 初始值j=i*i:初始倍数以i平方开始
               * i之前的倍数积有前面的素数将其修改
               * 如：i = 4，则 4*4=16 4*5=20 4*6=24 ...
               * 则在boolean数组的这些位置（16,20,24...）中标记为true（表示是非素数）
               * 而4*2 = 8、4*3 =12 则在前面的素数2和3那里已经修改了
               * j = j+i:实现j以i的倍数增长
               */
               for (int j = i * i;j < n;j += i){
        
                  isPrime[j] = true;
               }
           }
        }
        return count;
    }

#### 测试对比两个解法的时间 ####

如下图：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16]  
在数据量大时这两种算法的优劣性一目了然。

最后，面试时记得重点介绍第二种解法，第一种也可以提一下。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/8947c89d1b38412ea9b2e0ee01a07e96.png