一、定义法

// 1 定义法（除了1和他本身之外，没有任何一个数能被整除）（试除法）  bool is_prime3(unsigned long long n) { //slow      for (int i = 2; i < n - 1; i++) {          if (n % i == 0) {              return 0;          }      }      return 1;  }

二、定义法的改进

/*  根据如果一个数是合数，那么它的最小质因数肯定小于等于它的平方根。  用反证法可以证明一下。假设x是n的最小质因数，则存在n/x=p。p>x,x*p=n。如果x不小于等于它的平方根，则x*x>n,而p>x，故x*p>n,假设不成立。合数是与质数相对应的自然数。一个大于1的自然数如果它不是合数，则它是质数。也就是说如果一个数能被它的最小质因数整除的话，那它肯定是合数，即不是质数。所以判断一个数是否是质数，只需判断它是否能被小于它开跟号后的所有数整除，因此，这样做的运算少了很多，降低了时间复杂度。  */  int isprime(int m)  {      int i;      for(i=2;i<=sqrt(m);i++)    /*sqrt(int n)这个函数需要引入math.h头文件*/        if(m%i==0）          return 0;      return 1;  }

三、查表法

把一定范围内的素数都求出来直接复制到数组中，然后查询即可

四、孪生素数

/*  孪生素数： 所谓孪生素数指的是间隔为 2 的相邻素数，它们之间的距离已经近得不能再近了。  若n≥6且n-1和n+1为孪生素数，那么n一定是6的倍数。  证明：  ∵ n-1和n+1是素数 ┈┈┈┈┈ ①  ∴ n-1和n+1是奇数  ∴ n是偶数，即n是2的倍数 ┈┈┈┈┈ ②  假设n不是3的倍数，得：  n=3x+1 或 n=3x+2，  如果n=3x+1，则n-1=3x，与①违背，故n≠3x+1；  如果n=3x+2，则n+1=3(x+1)，与①违背，故n≠3x+2；  ∴假设不成立，即n是3的倍数，又有②得结论：  n是6的倍数。     由上面的规律可以推出下面结论：  若x≧1且n=6x-1或n=6x+1不是素数，那么n一定不是2和3的倍数。  证明：  ∵n=6x-1或n=6x+1，即n=2(3x)-1或n=2(3x)+1或n=3(2x)-1或n=3(2x)+1。  ∴n一定不是2和3的倍数。     素数出现规律：  当n≧5时，如果n为素数，那么n mod 6 = 1 或 n mod 6 = 5，即n一定出现在6x（x≥1）两侧。  证明：  当x≥1时，有如下表示方法：  ┈┈ 6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1┈┈  不在6x两侧的数为6x+2，6x+3，6x+4，即2(3x+1)，3(2x+1)，2(3x+2)，它们一定不是素数，所以素数一定出现在6x的两侧。  */  bool isPrime(int num)  {      if (num == 2 || num == 3)          return true;      if (num % 6 != 1 && num % 6 != 5)          return false;      for (int i = 5; i*i <= num; i += 6)          if (num % i == 0 || num % (i+2) == 0)              return false;      return true;  }

五、埃式筛法

首先，将2到n范围内的所有整数写下来。其中最小的数字2是素数。将表中所有2的倍数都划去。表中剩余的最小数字是3，它不能被更小的数整除，所以是素数。再将表中所有3的倍数全都划去。  依次类推，如果表中剩余的最小数字是m时，m就是素数。然后将表中所有m的倍数全部划去。像这样反复操作，就能依次枚举n以内的素数。    #include<iostream>  using namespace std;  int main() {  	int i,j,n,flag=1;  	bool a[100]= {0};  	for(i=1; i<=100; i++) {  		for(j=2; j<=100; j++) {  			a[i*j]=1;  		}  	}  	for(int p=0; p<=100; p++)  		if(a[p]==0) {  			cout<<a[p]<<" ";  		}  	return 0;  }

六、线性筛法（欧拉筛）

// 由于埃筛法做了许多不必要的循环，所以欧拉筛在埃筛法的基础上，省去了一些步骤，时间复杂度O(n)  int primes(int n)  {  	st[1] = true;  	for(int i=2;i<=n;i++)  	{  		if(!st[i])prime[++k] = i;  		  		for(int j=1;prime[j]<=n/i;j++)  		{  			st[prime[j] * i] = true;  			if(i % prime[j] == 0)break;  		}  	}  	return k;   }

(adsbygoogle = window.adsbygoogle || []).push({});