关于质数的判定与快速筛法

男娘i 2023-09-24 14:26 63阅读 0赞

一. 关于质数：

1.质数和合数是针对所有大于1的 “自然数” 来定义的(所有小于等于1的数都不是质数).  
2.所有小于等于1的整数既不是质数也不是合数.  
3.质数和素数都是同一种性质,只是叫法不同.

二.判定质数的方法：试除法（时间复杂度O(sqrt(n))）

(1).”d|n”代表的含义是d能整除n,(这里的”|”代表整除).  
(2).一个合数的约数总是成对出现的,两个数必定在sqrt(n)的左边和右边，因此我们判断一个数是否为质数的时候,只需要判断较小的那一个数能否整除n就行了,即只需枚举d<=(n/d),即dd<=n(可能会溢出),d<=sqrt(n)就行了.  
(3).sqrt(n)这个函数执行的时候比较慢.所以不常用，常用的为d<=(n/d).

![b5685d3c7c064249938d4143a730dc29.png][]

这是一道力扣题：计数质数，如果用试除法的话会超限

所以我们上算法：

三.埃氏筛法 时间复杂度:粗略估计:O(n).实际:O(nlog(logn)).

class Solution {
    public:
    int countPrimes(int n) {
        int num=0;//存储所有质数,num为用来计数
         vector<int> st(n,0);
         for(int i=2; i<n; i++){
            if(!st[i]){//没有被筛掉，说明是质数；
               num++;
               for(int j=2*i;j<n;j+=i) st[j]=1;//标记质数的倍数，一定是n里的合数，所以要筛掉
          }
         }
          return num;
        }
    };

(1).做法:把2~(n-1)中的质数的倍数都标记上,最后没有被标记的数就是质数.  
(2).原理:假定有一个数p未被2~(p-1)中的数标记过,那么说明,不存在2~(p-1)中的任何一个数的倍数是p,也就是说p不是2~(p-1)中的任何数的倍数,2~(p-1)中不存在p的约数,因此,根据质数的定义可知:  
p是质数.

[b5685d3c7c064249938d4143a730dc29.png]: https://img-blog.csdnimg.cn/b5685d3c7c064249938d4143a730dc29.png