对素数判断的查表

川长思鸟来 2022-03-06 11:22 82阅读 0赞

描述:

对于我们常见的素数问题大概就是判断和输出了,而我们常用的临界判断条件就是折半判断和平方根判断,显然后者相比前者所用时间更低一些.那还有没有其他的办法了呢?

*  肯定还有其他的方法,这里大概罗列两种方法 6倍原理和查表法

6倍原理:  
对于素数序列 2, 3, 5, 7, 11…我们可以发现除过2和3之外，其他的数字都是在6的倍数的旁边。于是，可以先判断是否6的倍数旁边来确实是否是素数，然后从剩下的里面排除是素数序列前面的元素是其因素的元素。

相关内容可以参考另外一个博主的文章  
[https://blog.csdn.net/qq\_36523667/article/details/78545682][https_blog.csdn.net_qq_36523667_article_details_78545682]

查表法：  
可以先从一段代码里面生成素数序列，把这个序列做成表或者文件查询就可以了

例如下面的代码：

\#include  
\#include  
\#include  
\#include  
\#include  
\#include  
using namespace std;  
vector<uint32\_t>prime;  
/\* 函数说明：  
\*函数名：void storedPrime(uint32\_t &num)  
\*参数说明：num 无符号32位变量，表示所要求得的质数不超过此值  
\*函数功能：结合6倍原理实现将不超过num的值存放到vector类型的容器里面  
\*函数输出：无  
\*时间复杂度：最坏：O(n^(3/2)) 最好：O(n)  
\*/  
void storedPrime(uint32\_t &num) //存储小于等于num的素数到容器里面  
\{  
char flag=0;  
prime.push\_back(2);  
prime.push\_back(3);  
for (int i = 5; i <= num; i += 2)  
\{  
if (i == 5 || i == 7)  
\{  
prime.push\_back(i);  
continue;  
\}  
if (i % 6 != 1 && i % 6 != 5)  
continue;  
for (int t = 5; t <= sqrt(i); t += 6)  
\{  
flag = 0;  
if (i%t == 0 || i % (t + 2) == 0)  
\{  
flag = 1;  
break;  
\}  
\}  
if (flag1)  
continue;  
prime.push\_back(i);  
\}  
\}  
int main()  
\{  
uint32\_t num = 0;  
uint32\_t count = 0;  
ofstream file(“prime.txt”,ios::out|ios::binary);  
cin >> num;  
if (num < 5)  
cout << 0;  
else \{  
storedPrime(num);  
file << “\{”;  
for (int i = 0; i < prime.size(); i++)  
\{  
file << setw(8)<<prime\[i\] << " ,";  
if ((i+1) %10 0)  
file << endl;  
\}

file << "}";
    	file.close();
    }
    system("pause");
    return 0;

\}  
对应的表部分如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjQyODI4_size_16_color_FFFFFF_t_70]

[https_blog.csdn.net_qq_36523667_article_details_78545682]: https://blog.csdn.net/qq_36523667/article/details/78545682
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjQyODI4_size_16_color_FFFFFF_t_70]: /images/20220303/10b9fa2eb6a94090ae23d49fafcdb4f9.png