素数

定义：

质数又称素数。一个大于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;//定义一个变量，若为合数，则该变量的值变为0for (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);
}

进制转换

我们只需要学会十进制与与任意进制之间相互转换就够了，任何题型都能够套这个公式。

十进制与任意进制之间相互转换：

接下来的步骤： 从下往上数余数，为 13123，所以：

其他进制转十进制：

下面给个例题（附带讲解）

十进制转 16 进制：