(C++)寻找1-100以内所有素数，复杂度为O(nsqrt(n))与O(nloglogn)的两种方法

本文主要是介绍(C++)寻找1-100以内所有素数，复杂度为O(nsqrt(n))与O(nloglogn)的两种方法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

注意：1既不是质数也不是合数，2是质数。

1. 复杂度为O(nsqrt(n))

原理：先写一个判断整数是否为素数的函数，其复杂度为sqrt(n)，其原理是对于一个数n，如果它有除了1和自身之外的因子，那么这个因子要么成对出现，一个在(1,sqrt(n))，另一个在(sqrt(n),n)。要么为sqrt(n)。因此只要判断(1,sqrt(n)]范围内有没有因子就好了。

判断函数的两种写法如下

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

说明：sqrt得到的结果为浮点型，强制转化为整型是对其向下取整

注意：i从2开始遍历

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;
}

注意：i*i可能溢出，最好声明i为long long型。 

2. 复杂度为O(nloglogn)

原理：用一个长度为101的布尔数组，存放1-100这100个数字是否为素数。从2开始，遇到一个素数，就把这个素数在100以内的所有倍数都初始化为false。

int main(){
	
	bool isPrime[maxn] = {1};//maxn = 101,默认都是素数，再筛去不是的 
	isPrime[2] = true;
	
	for(int i=2;i<maxn;i++){
		if(isPrime[i]){
			for(int j=i+i;j<maxn;j+=i){
				isPrime[j] = false;
			}
		}
	}	
	
	return 0;
}

 注意学习这里碰到一个素数，找它的倍数的方法。

这篇关于(C++)寻找1-100以内所有素数，复杂度为O(nsqrt(n))与O(nloglogn)的两种方法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！