基于求素数的数学题

1.首先来看一下如何最快最简单判断一个数是否是素数：

这个大佬的博客写的很好：https://blog.csdn.net/qq_45351611/article/details/120095631?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_aa&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_aa&utm_relevant_index=1

 1 bool isprime (int num)
 2 {
 3     if (num<=1) return 0;
 4     else if (num==2 || num==3) return 1;
 5     else if (num%6!=1 || num%6!=5) return 0;
 6     /*因为任何实数都可以表示成6x 6x+1 6x+2 6x+3 6x+4 6x+5的形式
 7     （当然也可以表示成5x+c,4x+c之类的，但用6x+c形式表示有更多的公因数可提出）
 8     6x+2 6x+3 6x+4 明显就有公因数不可能为素数；
 9     则只有6x+1 6x+5的奇数才可能为素数；*/
10     for (int i=5;i<=num/i;i+=6)
11         if (num%i==0 || num%(i+2)==0) return 0;
12         /*判断num作为6x+1或6x+5形式的奇数是否为素数
13         6x+1 6x+5若有因子，那么因子一定是6x+1 6x+5的形式
14         num%i来判断是否有6x+5形式的因子，num%(i+2)来判断是否有6x+1形式的因子*/
15     return 1;
16 }

2.接下来看一下看一下在0-n之间的素数如何最快求出：

欧拉筛法：

他是

2.埃氏筛的进化版：
埃拉托斯特尼筛法，利用当前已经找到的素数，从后面的数中筛去当前素数的倍数。

原理：每个大于1的正整数n都可以表示成素数之积的形式。所以在1到n中一个数若不是素数，一定会被筛到。

复杂度：O(n*lglgn),近似为O(n)。

缺点：会重复判断，如果数据很大会不好，如12，在素数2与素数3时就被判了两次；

bool number[maxn+5];
void isprime()
{
    int i,j;
    memset(number,true,sizeof(number));
    for(i=2;i<=maxn;i++)
    {
        if(number[i]==true)
        {
            for(j=2;j*i<=N;j++)
                number[i*j]=false;
        }
    }
}

而欧拉筛法只会遍历各个数一遍：

我们发现每个数都有最小质因数，且只有一个，如12的是2,18的是2,9的是3等等；

利用这个性质有：

 1 bool function (int num)
 2 {
 3     memset(isprime,0,sizeof (isprime));
 4     for (int i=2;i<=num;i++)
 5     {
 6         if (!isprime[i])
 7         {
 8             prime[cnt++]=i;
 9         }
10         for (int j=0;j)
11         {
12             isprime[prime[j]*i]=1;
13             /*如果i%prime[j]==0，如果接下来再i*prime[j+1]==num,那被标记的那个数num，并不是由最小质因数标价的
14             因为这表明i中有prime[j]才会i%prime[j]==0，如果i*prime[j+1]=num,这个num
15             会在后面又被标记一次；如：当i==4时，prime中有2,3；如果4*3了==12；
16             又i==6, 在prime[0]==2时，6*2==12,12被重复标记那这个算法与埃式筛法没区别了*/
17             if (i%prime[j]==0)
18             {
19                 break;
20             }
21         }
22     }
23 }