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

男娘i 2023-09-24 14:26 45阅读 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

发表评论取消回复

表情：

评论列表（有 0 条评论，45人围观）

还没有评论，来说两句吧...

相关阅读

相关筛法求质数

筛法求质数给定一个正整数 n，请你求出 1∼n 中质数的个数。输入格式共一行，包含整数 n。输出格式共一行，包含一个整数，表示 1∼n 中质数的个数

Myth丶恋晨/ 2024年03月31日 13:50/ 0 赞/ 84 阅读

相关【离线+筛法+MEX】阿宁的质数

一道蓝桥杯难度的题 [D-阿宁的质数\_牛客小白月赛56 (nowcoder.com)][D-_56 _nowcoder.com] 题意： ![09d1fffe18894

电玩女神/ 2024年03月16日 19:45/ 0 赞/ 62 阅读

相关关于欧拉筛法和普通筛法

为的是让一个合数只让最小的一个素数筛去 prime\[\]数组中的素数是递增的,当i能整除prime\[j\]，那么i\prime\[j+1\]这个合数肯定被pri

「爱情、让人受尽委屈。」/ 2024年02月17日 21:36/ 0 赞/ 78 阅读

相关质数 AcWing 868. 筛质数

质数 AcWing 868. 筛质数原题链接 [AcWing 868. 筛质数][AcWing 868.] 算法标签数学知识质数线性筛法筛法求素数

川长思鸟来/ 2023年09月28日 11:34/ 0 赞/ 2 阅读

相关质数 AcWing 868. 筛质数

质数 AcWing 868. 筛质数原题链接 [AcWing 868. 筛质数][AcWing 868.] 算法标签数学知识质数线性筛法筛法求素数

旧城等待，/ 2023年09月28日 11:34/ 0 赞/ 19 阅读

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

一. 关于质数： 1.质数和合数是针对所有大于1的 “自然数” 来定义的(所有小于等于1的数都不是质数). 2.所有小于等于1的整数既不是质数也不是合数. 3.质数和

男娘i/ 2023年09月24日 14:26/ 0 赞/ 46 阅读

相关质数的筛法

上一篇博客：[LeetCode 1006. 笨阶乘——每日一题][LeetCode 1006.] > 写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Acce

绝地灬酷狼/ 2022年11月15日 15:49/ 0 赞/ 205 阅读

相关质数中的质数（质数筛法

如果一个质数，在质数列表中的编号也是质数，那么就称之为质数中的质数。例如：3 5分别是排第2和第3的质数，所以他们是质数中的质数。现在给出一个数N，求>=N的最小的质数中的质数

迈不过友情╰/ 2022年06月11日 05:44/ 0 赞/ 183 阅读

相关 C语言——质数判定

Description 质数被定义为一个不能除了1和它本身整除的正整数。你的任务就是要编写一个程序，判定任意一个大于等于2的正整数是否是质数。 Input 输入只有一

亦凉/ 2022年03月21日 03:15/ 0 赞/ 219 阅读

相关数论——质数筛法

一、埃拉托斯特尼（Eratosthenes）筛法算法思想：　　要得到自然数n以内的全部素数，必须把不大于![5ab5c9ea15ce36d3884f4f0b39f33a

小灰灰/ 2021年11月10日 02:04/ 0 赞/ 450 阅读