第15课 函数、进制转换

Q1.判决素数个数

Q2.最大质因子序列

Q3.区间内的真素数

这一课的Q1-Q3都是与判断素数有关系，我们常常判断一个数n是否是素数的时候，从2开始试除，一直试除到sqrt(n)。当任务中需要有反复判断数字是素数时，上面的效率就太低了，可以选择先将可能用到的数字全部进行判断后，存放在一个数组里面，用的时候直接从数组里面获取就可以了。

#include <cstring>
#define ll long long
#define N 5000

ll a[N];

void prime()               //定义一个函数，求出所有N以内的素数，需要更大范围就修改N的值即可
{
	int i,j;
	memset(a,0,sizeof(a));        //初始化数组方法，需要<cstring>头文件 
	a[0]=a[1]=1;                  //0、1不是素数，在数组中标记成1
	for(i=2;i<=N/2;i++)           
		if(a[i]==0){
			for(j=2*i;j<=N;j=j+i)       //将不是素数的筛选出来，标记为1
				a[j]=1;	           //a[j]=1不是素数，a[j]=0是素数 
		}
}

Q4.二进制分类

先了解如何将一个十进制数转换成二进制数：参考文档