数论——质数（素数）
一：质数判断。
1.试除法（朴素版，O（o^2））
素数：只能被1和它本身整除。
故：遍历2-（n-1）;
int check(int n)
{if(n<2)return true;//特判for(int i=2;i2.试除法（稍优化O（√N））
1.假设p为一个合数，令p=a*b(a
2.求出一个数的因数，另一个因数为n/i（当n！=i），所以当我们判定其中一个（%i==0），则不必再判断后面的数。
eg：18=2*9；当我们遍历到4的时候就可以了。
int check(int n)
{if(n<2)return true;for(int i=2;i<=n/i;i++)//i*i=n可以写为：i=n/i；{if(n%i==0)return false;}return true;
}3.埃式筛法（如若题目数据为1e7及一下，则可以使用）
1.仅仅牢记素数的倍数一定不是素数。
我们从第一个素数2开始判断，将其倍数不断（true）消除。但是存在一个问题会重复消除同一个数的情况。
2.eg：2的倍数有，4，6~~~；
但是3的倍数也有6.所以重复删除了2次。
3.当数据过大时，浪费time
#include
#include
#include
using namespace std;
const int N=1e7+10;
int primes[N];
bool st[N];//最好使用bool定义.（原因不知，因为这样数据洛谷才给满分）
int k=0;
int get_prime(int n)
{for(int i=2;i<=n;i++){if(!st[i])//若未被消除，将i赋给primes[]{primes[++k]=i;}for(int j=i+i;j<=n;j+=i)//不断遍历i的倍数{st[j]=true;//素数的倍数一定不是素数，故此消除}}for(int i=1;i<=k;i++)cout< 4.欧拉筛选（当数据大于1e8时最好使用）
1在第一次就除余为0的时候就直接break；
2.避免重复的消除，导致浪费time
#include
#include
#include
using namespace std;
const int N=1e8+10;
int primes[N];
int st[N];
int k=0;
int get_prime(int n)
{for(int i=2;i<=n;i++){if(!st[i]){primes[++k]=i;}for(int j=1;primes[j]*i<=n;j++)//primes[j]*i<=n的作用是我要消除这个素数的倍数，但我的乘积不能大于我本身给的数{st[primes[j]*i]=true;if(i%primes[j]==0)break;//若第一个就可以除余，则后面就不用消除，避免重复。}}for(int i=1;i<=k;i++)cout<
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！