本文共 1821 字，大约阅读时间需要 6 分钟。

参考博客：

一、素数：（质数prime  number）定义为在大于1的自然数中，除了1和它本身以外不再有其他因数，素数有无穷多个。

先来两张素数分布表

 二、判断一个数n是否为素数

（一）最简单方法（从2到n-1每个数均整除判断）时间复杂度O(n)

int isPrime(int k){    int j;    for ( j=2; j

（二）开根号法：从2到n均整除判断，时间复杂度O(n)（原因：素数是因子为1和本身， 如果数c不是素数，则还有其他因子，其中的因子，假如为a,b.其中必有一个大于sqrt(c) ，一个小于sqrt(c) 。所以m必有一个小于或等于其平方根的因数，那么验证素数时就只需要验证到其平方根就可以了。即一个合数一定含有小于它平方根的质因子。）

int isPrime(int n){    int i;    for ( i=2; i<=sqrt(n); i++ )        {        if(n%i==0)    // 如果不为素数返回0     　　{           return 0;        }    }    return 1;    // 反之则返回1 }

三、判断1-n个数中的素数，并存下来

（一）开根法

//最普通的方法：#include
   
    #include
    
     #define N 10000001int prime[N];int main(){    int i, j, num = 0;for(i=2; i
     
      sqrt(i) ) prime[num++] = i;    }for(i=2; i<100; i++) //由于输出将占用太多io时间，所以只输出2-100内的素数。可以把100改为N    if( prime )printf("%d ",i);   return 0;}
     
    
   

（二）素数筛选法：就是当i是素数的时候，i的所有的倍数必然是合数。如果i已经被判断不是质数了，那么再找到i后面的质数来把这个质数的倍数筛掉。

算法具体实现

void compute_prime_table() //筛选法求出500000以内的所有素数{	int i,j;	p[0] = p[1] = 0;	for(i=2;i<=500000;i++)		p[i]=1; //初始化	for(i=2;i<=1000;)//对所有小于1000的素数，删除他们的倍数	{	for(j=i+i;j<=500000;j+=i)			p[j]=0;//删除i的所有倍数		for(i++;!p[i];i++);//找下一个素数}	for(i=0,k=0;i<=500000;i++)	{	if(p[i])		{	primes[k]=i;			k++;}	}}

（三）基于筛选法的素数求取方式

基于筛选法的素数求取方式：用数组的方式存取筛选候选集，根据质数的倍数不是质数，偶数不是质数的原则进行一次次筛选。

#include 
   
    #include 
    
     #define N 10000001int prime[N];int main(){   int i, j;   for(i=2; i
    
   

转载地址：https://blog.csdn.net/zhao2chen3/article/details/82955794 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！