蓝桥杯：C++素数、进制转换

素数

定义：

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin >> n;
	if(n == 1){
		cout  << n << "既不是素数也不是合数" << endl;
		return 0;
	}
	for(int i = 2;i<=sqrt(n);i++){
		if(n % i ==0){
			cout  << n << "不是素数" <<endl;
			return 0;
		}
	}
	cout  << n << "是素数" <<endl;
	return 0;
}

上面代码要是有疑惑，也只能是这段代码可能没有做过多的解释：

i<=sqrt(n)；

解释一下：

若 2 都不能除尽，还要试 4, 6, 8, …吗？若 3 都不能除尽，还要试 9, 15, 21, …吗？

这下就很清晰了。

测试一下程序，输入2等看看结果：

再测试一下：

可以看到是正常输出的，结果也是正确的。

素数区间统计（暴力法）

也就是找某个区间内有多少个素数

代码：

#include<bits/stdc++.h>
using namespace std;
//利用两层for循环，第一层遍历2-n的每一个数
//第二层判断这个数是不是素数
void brute_force(int n)
{
	int count = 0;//记录素数个数
	int i,j;
	int flag;//定义一个变量，若为合数，则该变量的值变为0
	for (i = 2; i <= n; i ++)
	{
		flag = 1;//先假定该数为素数
		for (j = 2; j<=sqrt(i); j ++)
		{
			if (i % j == 0)
			{
				flag = 0;//flag==0说明这个数是合数
				break;
			}
		}
		if (flag)
			count++;
	}
	printf("暴力算法 %d内有%d个素数\n", n, count);
}

int main(){
	//统计区间内的素数个数
	brute_force(5);//3个素数 
	return 0;
}

埃氏筛选

埃氏筛选的主要思想是先把n以内的合数全部找出来，合数排除以后，其余的就全部是素数了，运用的方法是以空间换时间。

void eratosthenes(int n)//埃氏筛选
{
	int no_prime[10000] = {0};//先假定全部为素数。找到一个数不是素数，就把这个值变为1     ---0是素数，1不是素数 
	int i, j;
	int count = 0;
	for (i = 2; i< n; i++)
	{
		if (!no_prime[i])//不是素数
		{
			count++;
			for (j = i * i; j < n; j += i)        
				no_prime[j] = 1;
		}
	}
	printf("埃氏筛选 %d以内有%d个素数", n, count);
}