一、题目
题目描述:
给你一个正整数N,在[2,N]这个区间内有多少个素数。
输入描述:
先输入一个整数T,代表有T(1<=T<=100000000)组数据,然后有T行正数N(1<N<=10000000).
输出描述
对于每一个N,输出在这[2,N]区间内,有多少个素数。
二、暴力素数筛
整体实现思想:两层循环,遍历每一个数,判断其是否为素数。
代码如下:
1 //暴力素数筛 2 vector<int> Find_Prime_number1(int n) 3 { 4 vector<int> ans; 5 6 //从2开始,1不是素数 7 for (int i = 2; i <= n; i++) 8 { 9 //默认是素数 10 int flag = 1; 11 //判断i是否是素数 12 for (int j = 2; j < i; j++) 13 { 14 if (i % j == 0) 15 { 16 flag = 0; 17 break; 18 } 19 } 20 if (flag) 21 ans.push_back(i); 22 } 23 24 return ans; 25 }
对其进行简单的优化,第二层的结束条件可以优化为sqrt(i),因为右面的所有数字都在面被遍历过。
代码如下:
1 //暴力素数筛优化 2 vector<int> Find_Prime_number2(int n) 3 { 4 vector<int> ans; 5 6 //从2开始,1不是素数 7 for (int i = 2; i <= n; i++) 8 { 9 //默认是素数 10 int flag = 1; 11 //优化循环结束调节,开方 12 for (int j = 2; j <= sqrt(i); j++) 13 { 14 if (i % j == 0) 15 { 16 flag = 0; 17 break; 18 } 19 } 20 if (flag) 21 ans.push_back(i); 22 } 23 24 return ans; 25 }
三、朴素素数筛(埃拉托斯特尼筛法)
整体实现思想:遍历到的每一个素数,将其的倍数设置为合数,避免对每一树的判断,可以大幅度节省时间,但是注意第二层循环的开始条件,从而i*i开始,而不是i*2。时间复杂度为O(n*loglogn)。
代码如下:
1 //朴素素数筛(埃拉托斯特尼筛法),时间复杂度为O(n * loglogn) 2 vector<int> Find_Prime_number3(int n) 3 { 4 vector<int> ans; 5 6 vector<bool> flag(n + 1, true); 7 8 //0和1不是素数,直接初始化好 9 flag[0] = 0; 10 flag[1] = 0; 11 12 //从2开始,1不是素数 13 for (int i = 2; i <= n; i++) 14 { 15 //如果当前数字是素数 16 if (flag[i]) 17 { 18 //i的倍数标记被不是素数 19 for (int j = i * i; j <= n; j += i) 20 { 21 flag[j] = false; 22 } 23 ans.push_back(i); 24 } 25 } 26 27 return ans; 28 }
四、线性素数筛(欧拉筛法)
整体实现思想:在朴素素数筛的过程中我们会重复筛到同一个数,例如12同时被2和3筛到,30同时被2、3和5筛到。所以我们引入欧拉筛,也叫线性筛,可以在 时间内完成对2~n的筛选。它的核心思想是:让每一个合数被其最小质因数筛到。
代码如下:
1 //线性素数筛(欧拉筛法),时间复杂度为O(n) 2 vector<int> Find_Prime_number4(int n) 3 { 4 vector<int> ans; 5 6 vector<bool> flag(n + 1, true); 7 8 //0和1不是素数,直接初始化好 9 flag[0] = 0; 10 flag[1] = 0; 11 12 //从2开始,1不是素数 13 for (int i = 2; i <= n; i++) 14 { 15 //如果当前数字是素数 16 if (flag[i]) 17 ans.push_back(i); 18 19 //显示标记合数 20 for (int j = 1; j <= ans.size() && i * ans[j-1] <= n; j++) 21 { 22 flag[i*ans[j - 1]] = false; 23 if (i % ans[j - 1] == 0) 24 break; 25 } 26 } 27 28 return ans; 29 }
五、参考文章
https://blog.csdn.net/qq_42685893/article/details/86761727
https://zhuanlan.zhihu.com/p/100051075#