从2到n枚举根号n次
bool isprime(int n){ for(int j=2;j*j<=n;j++){ if(i%j==0) return 0; } return 1; } 埃拉托斯特尼筛法基本思想：要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
表中有2到n的所有整数，其中2是最小的素数。将2记为素数，然后把表中2的倍数全部去掉。接下来表中最小的数是3，3不能被更小的数整除，所以3是素数，将表中所有3的倍数去掉。 以此类推，如果表中剩余的最小数为m,那么m就是素数，然后将表中m的倍数全部去掉。这样反复枚举就能够得到n以内的所有素数。
时间复杂度：O(nloglogn)。
#include<bits/stdc++.h> const int maxn=1e5; bool vis[maxn]; int prime[maxn],x=0; void Eprime(int n){//埃氏筛 for(int i=2;i<=n;i++){ if(!vis[i]) prime[x++]=i; for(int j=2;i*j<=n;j++){ vis[i*j]=1; } } } 欧拉筛法基本思想 ：在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。 时间复杂度：O(n) 任何合数都能表示为素数之积，所以每个合数一定有一个最小质因子，每个合数都被其最小质因子筛去过一次，所以是线性时间
void oprime(int n){//欧氏筛 for(int i=2;i<=n;i++){ if(!vis[i]) prime[x++]=i; for(j=0;j<x&&i*prime[j]<=n;j++){ vis[i*prime[j]]=1; if(i%prime[j]==0) break;//找到i*prime[j+k]的最小质因子为prime[j]，跳出循环 } } } 关于if(i%prime[j]==0)如果i%prime[j]==0,i是prime[j]的整数倍，那么记m=i/prime[j] 所以i=m*prime[j] 如果继续内层循环，j+1 设k=i*prime[j+1] 可以得到： k=i*prime[j+1]=(m*prime[j])*prime[j+1] =(m*prime[j+1])*prime[j] 这说明i*prime[j+1]是prime[j]的整数倍，即k是prime[j]的整数倍，prime[j]才是k的最小质因子，所以不需要再进行标记，跳出内层循环。 当之后外层循环枚举到i=m*prime[j+1]时，该数k=(m*prime[j+1])*prime[j]会在内层循环中被i*prime[j]标记。 对于prime[j+2]及之后的素数也是如此。 所以，为了避免重复标记，让循环在i%prime[j]==0时跳出
例如：
枚举2，2是素数，放入素数表，排除4枚举3，3是素数，放入素数表，排除6，9枚举4，4不是素数，执行下一步，排除8，4%2=0跳出内层循环，该内层循环原本下一个数是4*3=12枚举5，5是素数，放入素数表，排除10，15，20枚举6，6不是素数，排除12，18，这里12被6*2筛掉枚举7，7是素数，放入素数表，排除14枚举8，8不是素数，排除16，8%2=0跳出内层循环其中，如果第三步不在4中跳出，那么12将会被重复标记
