首页 > 编程语言 >算法3:质数的个数

算法3:质数的个数

时间:2023-05-01 22:33:48浏览次数:57  
标签:prime int 质数 个数 cin 算法 using include

一、质数的定义

质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。


二、判断质数的方法

1 for(int j = 2; j < i; j ++) {
2     if(i % j == 0)
3         break;
4     if(i == j)
5         cout << i << " ";
6 }

三、完整代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3  
 4 int main() {
 5     int n, k = 0, count = 1;
 6     //2直接输出 
 7     cin >> n;
 8     printf("2 ");
 9     for (int j = 2; j <= n; j++){
10         for (int i = 2; i < j ; i++) {
11             if (j % i == 0)
12                 break;
13             else if ((j % i != 0) && (i == (j-1)))
14                 k = j;
15             else
16                 continue;
17             count ++;
18             printf("%d ", k);
19         }                
20     }
21     printf("\n1-%d有%d个素数", n, count);
22     return 0;
23 }

四、优化

当我们的数据比较小的时候,我们当然可以使用双重循环的暴力做法找到质数,但是当数据较大时,时间复杂度会随之变大,我们可以通过sqet(n)进行第一次优化。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main() {
 5     int N, count = 0;
 6     cin >> N;
 7     for (int n = 1; n <= N; n ++) {
 8         for (int i = 2; i <= sqrt(n); i ++) {
 9             if (n % i == 0)
10                 break;
11         }
12         if (j < i)
13             printf("%d ", n);
14             count ++;
15     }
16     printf("\n1-%d有%d个素数", N, count);
17     return 0;
18 }

埃氏筛

首先将2到n范围内的整数写下来。

其中2是最小的素数,将表中所有的2的倍数划去。

表中剩下的最小的数字就是3,他不能被更小的数整除,所以3是素数。

再将表中所有的3的倍数划去…… 以此类推,如果表中剩余的最小的数是m,那么m就是素数。

然后将表中所有m的倍数划去,像这样反复操作,就能依次枚举n以内的素数。

埃氏筛法的时间复杂度是0(n*log(logn))。

 1 #include<iostream>
 2 using namespace std;
 3 const int N = 1e8 + 10;
 4 bool isprime[N];
 5 
 6 int main() {
 7     int n, i, ans;
 8     cin >> n;
 9     for(int i = 0;i < N; i ++)
10         isprime[i] = true;
11 //     isprime[0] = false;
12 //     isprime[1] = false;
13     for(int i = 2; i <= n; i ++) {
14         if(isprime[i]) {
15             for(int j = i * 2; j <= n; j += i){
16                 //筛掉前面素数的倍数
17                 isprime[j] = false;
18             }
19         }
20         if(isprime[i])
21             ++ ans;
22     }
23     cout << ans;
24     return 0;
25 }

对于较大的数据,这个代码是不能AC的,我们需要进一步的优化。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 bool a[100000005];
 4 int main() {
 5     int n, ans = 0;
 6     cin >> n;
 7     for(int i = 2; i * i <= n; ++ i) {
 8         if(a[i] == 0){
 9             for(int j = i * i; j <= n; j += i) {
10             //这里直接j=i*i,而不用j=i*2;因为前面有2*i,3*i,4*i....,(i-1)*i
11                 a[j] = 1;
12             }
13         }
14     }
15     for(int i = 2; i <= n; ++ i) {
16         if(a[i] == 0)
17             ++ ans;
18     }
19     cout << ans;
20     return 0;
21 }

欧拉筛(线性筛)

欧拉筛法的原理同埃氏筛法,多了一个判断删除与标记最小质因子的过程。

在埃氏筛法中,一个合数来说可能会被筛多次,比如6可以被2筛去,也可以被3筛去,而欧拉筛要做的事情就是让一个合数只被筛一次。

首先,任何合数都能表示成多个素数的积。所以,任何的合数肯定有一个最小质因子。我们通过这个最小质因子就可以判断什么时候不用继续筛下去了。

首先看核心代码:

 1 void ola(int n)
 2 {
 3     for (int i = 2; i <= n; i ++ )
 4     {
 5         if (st[i] == 0) primes[cnt ++ ] = i;//将质数存到primes中
 6         for (int j = 0; primes[j] <= n / i; j ++ )//要确保质数的第i倍是小于等于n的。
 7         {
 8             st[primes[j] * i] = 1;
 9             if (i % primes[j] == 0) break;
10         }
11     }

再看完整代码:

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int v[100001000]; //v[i]=a代表数i的最小质因数为a 
 5 int prime[600000]; 
 6 int cnt = 0;
 7  
 8 void is_prime(int n) {
 9     v[0] = v[1] = 1;
10     for(int i = 2; i <= n; ++ i) { //注意这里也统计了等于n的数 
11         if(! v[i]){ 
12             v[i] = i;
13             prime[++ cnt] = i;
14         } 
15         for(int j = 1; j <= cnt; ++ j) {
16             if(prime[j] > n / i || prime[j] > v[i])
17                 break; 
18             v[i * prime[j]] = prime[j];
19 
20         }
21     }
22 } 
23  
24 int main(){
25     int n, q;
26     cin >> n >> q;
27     is_prime(n);
28     for(int i = 0; i < q; ++ i) {
29         int k;
30         cin >> k;
31         cout << prime[k] << endl;
32     }
33     return 0;
34 } 

 

标签:prime,int,质数,个数,cin,算法,using,include
From: https://www.cnblogs.com/wanyy-home/p/17367121.html

相关文章

  • 推荐算法的知识框架【更新中】
    几年前刚进入行业时,就简单认为不过是wide&deep做精排,双塔FM做召回做粗排,再加上一些周边项目,比如冷启动和多模型融合调参,就组成了一个完整的推荐系统算法部分。再回头思考这一切,不再迷失在各式各样的实现细节中,关注本质,有了更广泛的认识,分为一下几个部分。1.建模方法多阶段的推......
  • 判断是不是质数
    importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();booleanisPrime=true;for(inti=2;i<n;i++){......
  • 整理一些学过的数据结构和算法
    匆匆忙忙中学了很多算法,但基本都是打个板子就跑路了,有些算法有个人比较深入和独特的见解,但大部分,只是实现例题的需求,对算法的作用似懂非懂,所以写篇博客整理一下。无旋平衡树(treap)高级数据结构:树和堆可以允许的操作:插入,删除,查询某数排名,查询某排名的树(第K大),求某数的前驱,后驱(X......
  • 数据有偏差,照样能学对!20年前就有这么强的算法了?
    文|白鹡鸰给小铁比了个心编|小轶背景“每个人都依赖自己的知识和认知,同时又为之束缚,还将此称为现实;但知识和认识是非常暧昧的东西,现实也许不过是镜花水月——人们都是活在偏见之中的,你不这样认为吗?这双眼睛,又能看多远呢?”机器学习,作为模仿人类思维方法进行建模的过程,虽然从数......
  • 【字节二面算法】NO662 二叉树最大宽度
    [字节二面算法]662.二叉树最大宽度给你一棵二叉树的根节点root,返回树的最大宽度。树的最大宽度是所有层中最大的宽度。每一层的宽度被定义为该层最左和最右的非空节点(即,两个端点)之间的长度。将这个二叉树视作与满二叉树结构相同,两端点间会出现一些延伸到这一层的n......
  • 「学习笔记」SPFA 算法的优化
    与其说是SPFA算法的优化,倒不如说是Bellman-Ford算法的优化。栈优化将原本的bfs改为dfs,在寻找负环时可能有着更高效的效率,但是最坏复杂度为指数级别。voiddfs_spfa(intu){ if(fg)return; vis[u]=true; for(pilit:son[u]){ intv=it.first; llw=......
  • 线索化二叉树的递归算法
    //线索化二叉树的递归算法#include<stdio.h>#include<malloc.h>typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;//存储二叉树的左孩子和右孩子}BiTNode,*BiTree;typedefstructThreadNode{intdata;structThreadNode*......
  • m分别使用meanshift和camshift两种算法实现人员跟踪并输出人员移动曲线matlab仿真
    1.算法仿真效果matlab2022a仿真结果如下:    2.算法涉及理论知识概要       meanshift算法其实通过名字就可以看到该算法的核心,mean(均值),shift(偏移),简单的说,也就是有一个点,它的周围有很多个点 我们计算点 移动到每个点 所需要的偏移量之和,求平均,就得到......
  • 文心一言 VS chatgpt (13)-- 算法导论3.1 8题 3.2 1题
    八、可以扩展我们的记号到有两个参数n和m的情形,其中的n和m可以按不同速率独立地趋于无穷。对于给定的函数g(n,m),用O(g(n,m))来表示以下函数集:O(g(n,m))={f(n,m):存在正常量c、和,使得对所有n>=n0或m>=m0,有0<=f(n,m)<=cg(n,m)}对Ω(g(n,m))和θ(g(n,m))给出相应的定义。文......
  • 文心一言 VS chatgpt (13)-- 算法导论3.1 8题 3.2 1题
    八、可以扩展我们的记号到有两个参数n和m的情形,其中的n和m可以按不同速率独立地趋于无穷。对于给定的函数g(n,m),用O(g(n,m))来表示以下函数集:O(g(n,m))=对Ω(g(n,m))和θ(g(n,m))给出相应的定义。文心一言:chatgpt:类比于单个参数的情形,我们可以定义类似的记号:O(g(n,......