统计小于N的质数/找到小于的N的全部质数

比眉伴天荒 2023-06-15 06:37 11阅读 0赞

> 1、所有文章优先发表在个人博客上： [https://www.xdx97.com][https_www.xdx97.com]  
> 2、后续如果有修改的话，可能忘记更新到CSDN了，给你带来不便，抱歉。  
> 3、个人博客本篇文章地址 ： [https://www.xdx97.com/article?bamId=646403272499789824][https_www.xdx97.com_article_bamId_646403272499789824]

> 这个题在大一学c的时候就遇到了，一直也没太注意。比较简单不是？  
> 你只要搞清楚什么是质数就好了。  
> 质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。  
> 但是我今天遇到了一个题 **统计小于N的质数**，却因为算法时间复杂度无法做出来。  
> 下面给出三种方法，最后一种是最好的统计。

**为了代码简洁，下面默认 n >2,不要有杠精…**

## 1、从2到n-1去判断是否可以被整除的 ##

public int fun(int n){ 
            int sum = 1,flag = 0;
            for (int m = 3; m < n; m++){ 
                flag = 0;
                for (int i = 2;i < m; i++){ 
                    if (m % i == 0){ 
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0){ 
                    sum ++;
                }
            }
            return sum;
        }

## 2、从2到 根号n 去判断是否可以被整除的 ##

public int fun(int n){ 
            int sum = 1,flag = 0;
            for (int m = 3; m < n; m++){ 
                flag = 0;
                double k = Math.sqrt(n);
                for (int i = 2;i < k; i++){ 
                    if (m % i == 0){ 
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0){ 
                    sum ++;
                }
            }
            return sum;
        }

## 3、厄拉多塞筛法 ##

/** * 思路： * 这题搜到一个非常牛逼的算法,叫做厄拉多塞筛法. * 要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。 * 给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下， * 把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉； * 接下去用下一个质数5筛，把5留下，把5的倍数剔除掉； * 不断重复下去…。 * * @author 小道仙 * @date 2019年11月19日 */
        public int countPrimes (int n ){ 
            int sum = 0;
            boolean[] bool = new boolean[n+1];
            for (int i = 2;i < n; i++){ 
                if (bool[i] == false){ 
                    sum ++;
                    for (int j = 2; j*i < n; j++) { 
                        bool[j*i] = true;
                    }
                }
            }
            return sum;
        }

[https_www.xdx97.com]: https://www.xdx97.com/
[https_www.xdx97.com_article_bamId_646403272499789824]: https://www.xdx97.com/article?bamId=646403272499789824