C++质数判断_判断质数c++时间复杂度

---

title: C++ 关于判断整数N是不是质数（素数）的基本算法
date: 2020-02-06 20:16:55
tags:

质数的定义：一个大于1的自然数，除了1和它本身外，不能被其他自然数（质数）整除。

no.1(时间复杂度O(N))

判断整数N是不是质数，只需要用N除以2到N-1，如果都不能整除，那么该数就是质数

no.2(时间复杂度O(sqrt(N)))

判断整数N是不是质数，只需要用N除以2到sqrt(N)，如果都不能整除，那么该数就是质数

no.3(时间复杂度O(sqrt(N)/2))

在no.2基础上去掉偶数的判别，因为大于2的偶数不可能是质数

no.4(时间复杂度O(sqrt(N)/3))

大于等于5的质数一定和6的倍数相邻

#include<iostream>
#include<cmath>
using namespace std;
bool is_prime1(int n)
{
	bool flag=true;
	if(n==2)
		return flag;
	if(n%2==0||n==1)
	{
		flag=false;
		return flag;
	}
	for(int i=2;i<n-1;i+=2)
	{
		if(n%i==0)
			flag=false;
	}
	return flag;
}
bool is_prime2(int n)
{
	bool flag=true;
	if(n==2)
		return flag;
	if(n%2==0||n==1)
	{
		flag=false;
		return flag;
	}
	double N=static_cast<double>(n);
	int temp=static_cast<int>(sqrt(N));
	for(int i=2;i<=temp;i+=2)
    {
		if(n%i==0)
			flag=false;
	}
	return flag;
}
bool is_prime3(int n)
{	
	bool flag=true;
	if(n==1){flag=false;return flag;}
	else if(n==2 || n==3) {return flag;}
	else if(n%6!=1 && n%6!=5){flag=false;return flag;}
	else
	{	
		double n_sqrt=sqrt(static_cast<double>(n));
	    int temp=static_cast<int>(n_sqrt);
		for(int i=5;i<=temp;i+=6)	
		{	    
			if(n%i==0 ||n%(i+2)==0) flag=false;
		}
		return flag;
	}
} 
int main()
{
	int n;
	cout<<"please input 整数n："<<endl;
	cin>>n;
	int count=0;
	int*prime=new int[n];
	for(int i=1;i<=n;i++)
	{
		if(is_prime3(i))
		{
			prime[count++]=i;			
		}
	}
	for(int i=0;i<count;i++)
		cout<<prime[i]<<"  ";
	delete[]prime;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

​
​