面试准备（十）素数个数统计

柔光的暖阳◎ 2022-10-12 15:55 145阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzcxNTY3_size_16_color_FFFFFF_t_70][]

**解题思路一：**

暴力解法：每个数n都计算与n-1之内的数能否整除（后期可以优化到与2-根号n之间）。

**解题思路二：**

埃筛法：利用合数的概念，素数\*n必然是合数，因此可以从2开始遍历，将所有合数提前做上标记，减少计算。

**代码：**

public class PrimeNumber {
    
        public static void main(String[] args) {
            System.out.println(bf(100));
            System.out.println(eratosthenes(100));
        }
    
        //暴力算法
        public static int bf(int n){
            int count = 0;
            for (int i=2;i<n;i++){
                count += isPrime(i)?1:0;
            }
            return count;
        }
    
        //只需要计算到根号x即可，因为超过根号x计算会重复
        public static boolean isPrime(int x){
            for (int i=2;i*i<=x;i++){
                if (x%i==0){
                    return false;
                }
            }
            return true;
        }
    
        //埃筛法 素数的乘积肯定是合数,将合数位改为true
        public static int eratosthenes(int n){
            boolean[] isPrime = new boolean[n]; //false代表素数
            int count = 0;
            for (int i=2;i<n;i++){
                if(!isPrime[i]){
                    count ++;
                    //i*i 是为了降低计算次数
                    for (int j=i*i;j<n;j+=i){
                        isPrime[j] = true;
                    }
                }
            }
            return count;
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzcxNTY3_size_16_color_FFFFFF_t_70]: /images/20221005/d10674c73c4e4593b2d3a4c89caf5e02.png