求素数的优化

学习自:传送门

1.一个一个找,找因子直到i

2.找因子直到i/2

比如:判断i是否为素数,则看i是否能整除j=2~i/2

3.找因子直到根号i

比如:判断i是否为素数,则看i是否能整除j=2~根号i

因为对于16,根号16=4,那么判断8是16因子就没必要了,因为2*8=16,如果已经找到8,那么肯定找到2了

如果根号i前没有i的因子,那么根号i后面也没有因子,因为因子必定是一个:

小于等于根号i的数*大于等于根号i的数==i

这里有两种方法

@1:j*j<=i

@2:j和根号i对比

我之前用第二种方法,但是好像容易出问题,因为那个浮点数到整型的边界不好处理,所以这里哪怕第一种效率差一点,我也推荐用第一种

4.除了0和2以外的偶数都不是素数

然后只用判断计数就好了,这里的j可以用+=2来递增,因为跳过偶数嘛

5.埃氏筛法:一个数的倍数肯定不是素数

比如说11的倍数22,33,44,55,121...都不是素数,都可以用筛子筛选掉

6.最优版

看到睡着了都没看懂,先留下别人的代码,下次再学

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000;
int prime[maxn];//定义在外面,初始值为0
int a[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    int i,j,len=0;
    for(i=2;i<=maxn;i++)
    {
        if(prime[i]==0)
            a[len++]=i,cout<<i<<endl;
        for(j=0;j<len&&a[j]*i<=maxn;j++)
        {
                prime[a[j]*i]=1;
                if(i%a[j]==0)break;
        }
    }
}