计算数论--素数判断及算法

Posted on 2018-02-23

Letcode题目

素数(也叫做质数):一个大于1的自然数,除了1和它本身外没有其他的约数。也就是在2到n-1之间的数除它都除不尽。(注意1不是素数)

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

当n特别大的时候,复杂度太高了,如果一个数不是素数,必然可以因式分解成 axb, a和b必然分处sqrt(n)的左右两边。

bool isPrime(int n)
{
    int upper = sqrt(n);
 	for(int i = 2;i<=upper;i++)
 	{
 		if(n % i == 0)
 		return flase;
 	}
 	return true;
}

素数筛选–埃拉托斯特尼筛法

要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,剩下的就是素数。

  • 做法:

给出要筛数值的范围n,找出以内的素数。

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

先用2去筛,即把2留下,把2的倍数剔除掉;

2 3 5 7 9 11 13 15 17 19 21 23 25 27 29

再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;

2 3 5 7 11 13 17 19 23 25 29

接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去……。

class Solution {
public:

	int countPrimes(int n)
	{
	    //对应的标记
		vector <bool> prime_mark;

		for (int i = 0; i < n; i++)
		{
		    // 0,1 都不是素数
			if (i<2)
				prime_mark.push_back(false);
			
			//初始余下所有小于的数都是素数
			
			else
				prime_mark.push_back(true);
		}
		
		//计算素数的数目
		int cnt = 0;

		for (int j = 2; j < sqrt(n); j++)
		{
		    //如果当前是素数
			if (prime_mark[j] == true)
			{
			    //将当前素数的倍数的数都标记为合数
				for (int k = j * 2; k < n; k = j + k)
				{
					prime_mark[k] = false;
				}

			}
		}

		for (int j = 2; j < n; j++)
		{
			if (prime_mark[j] == true)
			{
			   //愿意的话可以输出当前素数
			   //加一句cout<<j<<" ";
				cnt++;
			}
				
		}
		return cnt;
	}
};

复杂度 时间 O(sqrt(n))

空间 O(N)

此外还有欧拉筛法,之后补充 贴其他收藏:

表达式

函数模板


蚊子再小也是肉~
本站总访问量 本站访客数