素数最简单的判断方法是采用枚举，复杂度为O（n）。（这里不作解释）

这里将介绍下列几点：
1）素数判断，复杂度为O（√n）的原理及代码。
2）素数表的获取。
3）更为高效判断素数的"筛选法"。

（一）素数判断
这里介绍复杂度为O（√n）的原理：
例：2~n-1中存在n的约数，不妨设为k，即n%k==0，那么由k*（n/k）==0，n/k也是n的一个约数，因此得到了k与n/k中一定满足：一个数小于√n，一个数大于√n。
这里稍作解释：√n*√n=n，而k*n/k=n，因此一个约数小于√n，一个约数大于√n。
启示：只需判断n能否被2，3...，|_√n_|中的一个整除即可（其中|_√n_|表示向下取整）。

在此注意sqrt()函数的用法：
1）传入的参数应为浮点型。
2）返回的类型也为浮点型。

因此：请严格按照标准来书写代码。

bool isPrime(int n){
	if(n<=1) return false;
	int sqr=(int)sqrt(1.0*n);
	for(int i=2;i<=sqr;i++){
		if(n%i==0) return false;
	}
	return true;
}

可能你还有看到其他更为简单的写法如：

bool isPrime(int n){
	if(n<=1) return false;
	for(int i=2;i*i<=n;i++){
		if(n%i==0) return false;
	}
	return true;
}

建议新手不要使用此简单的写法，原因：在n接近int类型范围上界时，i*i极有可能越界溢出。（当然n在10^9以内是绝对安全的）
不过这也是有解决办法的：将i定义为long long类型即可。

（二）获取表
方法：从1~n枚举，判断每个数是否为素数。
时间复杂度：一部分O（n），另一部分O（n√n），因此获取表的复杂度为O（n*n√n）。

#include <stdio.h>
#include <math.h>

//求100以内素数表 
bool isPrime(int );
int prime[101],Num=0;
void Find_Prime(){
	for(int i=1;i<101;i++){
		if(isPrime(i)==true){
			prime[Num++]=i;
		}
	}
}

//判断n是否为素数 
bool isPrime(int n){
	if(n<=1) return false;
	int sqr=(int)sqrt(1.0*n);
	for(int i=2;i<=sqr;i++){
		if(n%i==0) return false;
	}
	return true;
}
int main(){
	Find_Prime();
	for(int i=0;i<Num;i++) {
		printf("%d ",prime[i]);
	}
	return 0;
} 

（三）筛选法求素数
原理：把2到n中所有的数都列出来，然后从2开始，先划掉n内所有2的倍数，然后每次从下一个剩下的数（必然是素数）开始，划掉其n内的所有倍数。最后剩下的数，就都是素数。

具体过程：自己百度。

int prime[101],Num=0;
bool p[101]={0};//如何为素数则为false 
void Find_Prime(){
	for(int i=2;i<101;i++){
		if(p[i]==false){
			prime[Num++]=i;
			for(int j=i+i;j<101;j=j+i){
				p[j]=true;
			}
		}
	}
}

时间复杂度为O(nloglogn)

欢迎访问最新博客地址

最近在复习之前做的编程练习题，素数判断一直没有掌握，今天看到了一种新的方法，感觉特别好，记下来。（第一次写博客，很开心呀）
思想来源,看不懂我的,欢迎看原作

素数的一些性质吧

1. 素数的分布规律
   大于5的素数一定于6的倍数相邻,例如5和7,11和13,17和19等等。
2. 证明
   令 x ≥ 1,则大于5的自然数可以表示如下:
   …6x-1, 6x, 6x+1, 6x+2, 6x+3, 6x+4, 6x+5,6(x+1)-1…
   可以看到,不在6的倍数的两侧的6x+2, 6x+3, 6x+4,由于上式可表示为2(3x+1), 2(2x+3), 2(3x+2),So 他们一定不是素数,在除去6x本身,显然素数只能出现在6的倍数的两侧,但这只是素数的必要条件可不是充分必要条件,所以在6的倍数的两侧的数也不一定素数。
3. 孪生素数
   题外话，放个题拿走练练

C++代码实现与解析

明确目的: 找到可以整除的数(这很重要)
实现:

• 首先对两个较小的素数进行处理
• 接下来判断这个数是否在6的倍数的两侧,不是的话直接返回0,是的话接着处理
• 由于一个数N如果可以被另一个数m整除，那m一定小于N的开方,没啥问题。所以我们就取判断的上界为N的开方。为了更快呢，直接取 i 的每次递增6，原因是，假如要判断的数为N，那N一定可以表示为6x-1或6x+1，对于循环中的 i 也可以表示为6的倍数加上或减去个数字，即6m-1，6m，6m+1，6m+2，6m+3，6m+4，如果N能被6m，6m+2，6m+4，整除那N至少是一个偶数，显然第二步已经把偶数排除了，所以不可能成立，而对于6m+3如果成立则N至少是3的倍数，但6x是3的倍数，显然6x+1，6x-1可能被3整除，所以N也不可能被6m+3整除，那现在就只剩下了6m-1，6m+1了，只需判断它俩能否把N整除，如果可以那就存在了一个数可以把N整除，就返回0。反之就不存在了，那就走到了最后就返回1，哈哈大功告成。

bool isPrime(int num)
{
    // 两个较小的数另外处理
    if(num == 2 || num == 3)
    {
        return 1;
    }
    // 不在6的倍数的两侧的一定不是素数
    if(num % 6 != 1 && num % 6 != 5)
    {
        return 0;
    }
    int tem = (int)sqrt(num);
    //在6的倍数的两侧的也不一定是素数
    for(int i = 5;i <= tem;i += 6)
    {
        if(num % i == 0 || num % (i + 2) == 0)
        {
            return 0;
        }
    }
    // 排除所有剩余的是素数
    return 1;
}

人生第一篇博客，如有错误欢迎指正讨论。谢谢我自己，也谢谢大家

判断素数最快的方法

1、普通方法

bool is_prime(int n)
{
    if (n < 2)
        return false;
    int i;
    for (i = 2; i < n; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
    return true;
}

原理是对每个数进行开方，模运算。
我们来统计0~100000之间有多少素数，并计算程序运行的时间。

int main()
{
    clock_t start, finish;
    double totaltime;
    start = clock();
    int n = 0;
    for (int i = 0; i < 100000; i++)
    {
        if (is_prime(i))
        {
            n++;
        }
    }
    cout << "n = " << n << endl;
    finish = clock();
    totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
    cout << "\n此程序的运行时间为" << totaltime << "秒！" << endl;
    return 0;
}

运行结果如下：

n = 9592
此程序的运行时间为1.244秒！

平时需求不太大，勉勉强强能接受这个速度吧。
但是范围增加到0~1000000，

for (int i = 0; i < 1000000; i++)

n = 78498
此程序的运行时间为102.255秒！

这个时间太长了。如果数据量再大一点，那我岂不是要等到天荒地老？

2、目前我发现的最快的方法

n>3时，对一个数字进行模6运算，如果结果是0,2,3,4，那么这个数肯定不是素数。

这样就节省了2/3的工作量。

接下来和第一种方法类似，不过是从5开始，步长为6，
除数i和i+2都是奇数并且都是质数，这又减少了特别多的工作量。

bool is_prime(int num)
{
    if (num <= 3)
        return num > 1;
    if (num % 6 != 1 && num % 6 != 5)
        return false;
    int s = sqrt(num);
    for (int i = 5; i <= s; i += 6)
        if (num % i == 0 || num % (i + 2) == 0)
            return false;
    return true;
}

现在运行一下0~100000的结果：

for (int i = 0; i < 100000; i++)

a = 9592
此程序的运行时间为0.005秒！

0.005秒，跟1.244秒比，速度是原来的248.8倍。

接下来

for (int i = 0; i < 1000000; i++)

n = 78498
此程序的运行时间为0.064秒！

0.064秒相比于102.255秒，速度增加1597.7倍！简直是一个天上一个地下。

接下来再增大范围：

for (int i = 0; i < 10000000; i++)

n = 664579
此程序的运行时间为1.43秒！

for (int i = 0; i < 100000000; i++)

n = 5761455
此程序的运行时间为36.375秒！

行了行了，到此为止。