质数是针对所有大于1的自然数定义的，在大于1的整数中，如果只包含1和本身这两个约数，就被定义成为质数，或者叫素数。
一个数的因数都是成对出现的：例如12的因数有3和4,2和6
所以我们可以只枚举较小的那一个，即根下n，假设较小的为d，较大的为n/d；
#include<iostream>
#include <algorithm>
using namespace std;
bool is_prime(int x)
{
if (x < 2) return false;
//只枚举到较小的约数，不推荐用sqrt(n)，比较慢；i * i <= x容易溢出。不推荐
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
int main()
{
int n;
cin >> n;
while (n -- )
{
int x;
cin >> x;
if (is_prime(x)) puts("Yes");
else puts("No");
}
return 0;
}
质因数的定义：
首先我们应该了解一下正常的教学做法：
所以我们只需要进行这些步骤的模拟即可，也就是从2开始遍历循环不停的进行除法：
步骤详解
从2开始往后做除法，第一个能被除开的数一定是原数n的一个质数
for(int i=2;i<=n/i;i++)
if(n%i==0)
如果这个数是，那么继续对这个数轮番进行除法，且记录指数
int s=0;
while(n%i==0)
{
n/=i;
s++; //指数
}
而如果除到最后n>1那么说明最后的这个n也是n的一个质数
为什么可以这样？
因为
n中最多只包含一个大于根号n的质因子
if(n>1)printf("%d %d\n",n,1);
代码实现：
#include<bits/stdc++.h>
using namespace std;
void divide(int n){
for(int i=2;i<=n/i;i++){
if(n%i==0){ //n不包含任何从2到i-1之间的质因子（已经被除干净了）
//(n%i==0)所以i也不包含何从2到i-1之间的质因子，由质数的定义可知，保证了i是质数
int s=0;
while(n%i==0) n/=i,s++;
cout<<i<<' '<<s<<endl;
}
}
if(n>1) cout<<n<<' '<<1<<endl; //最多只有一个大于根下n的质因子（两个相乘就大于n了）
cout<<endl;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
int a;
cin>>a;
divide(a);
}
}
（1）普氏筛法
思想：
i从2开始遍历到n，将i所有小于n的倍数全部划掉，剩下的便是质数。
特点：
好记
时间复杂度:
O
(
n
l
o
g
n
)
O( nlogn)
O(nlogn)
代码
void get_primes()
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i; //如果没被划过，就存入数组中
for (int j = 0; j <= n; j += i)//不管是合数还是质数，都用来筛掉后面它的倍数
{
st[j] = true; //将i的倍数划掉
}
}
}
（2）埃氏筛法（埃及人发明的筛法）
思想:
其实跟普氏筛法差不多，只是只用质数去筛，因为合数筛掉的数肯定已经被比它小质数筛掉了，不需要再筛，所以只用质数筛即可。
特点：
思考简单
时间复杂度：
O
(
n
l
o
g
l
o
g
n
)
O(nloglogn)
O(nloglogn)
代码
void get_primes()
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
for (int j = i; j <= n; j += i)
{ // 放到了里面（唯一区别）
st[j] = true;//可以用质数就把所有的合数都筛掉；
}
}
}
}
(3) 线氏筛法
核心思想: 合数
x
x
x 只会被其最小质因子筛掉一次
为方便表述, 定义一个只有本文使用的术语:
“最小质因子左乘的方式” 表: 若 a × b = x a×b=x a×b=x, 则 a a a 表示 x x x 的最小质因子
算法过程
算法的主要逻辑是一个 for i = 2 to n 循环
循环的每一轮会做这样一个事情:
筛去以 “最小质因子左乘 i i i的方式” 得到的合数 x x x, 即:
筛去 a × i = x a×i=x a×i=x, a ≤ i a≤i a≤i, a a a为 x x x的最小质因子得到的合数 x x x
例:
注意:
3
×
4
3×4
3×4 并未在
i
=
4
i=4
i=4时被筛掉, 因为其会在
i
=
6
i=6
i=6时以 “最小质因子左乘的方式” 被
2
×
6
2×6
2×6 筛掉
代码
int primes[N], cnt; // 记录得到的素数
bool st[N]; // 标记元素是否被筛掉
void get_primes(int n)
{
for(int i = 2; i <= n; i++)
{
if(!st[i]) primes[cnt++] = i; // 循环到 i 时, 算法暗含 1 ~ i-1 的所有合数都被筛掉, 只剩素数
for(int j = 0; primes[j] <= n / i; j++) // 算法不会闲的没事干筛去 primes[j] * i > n 的数
{
st[primes[j] * i] = true; // 筛掉以最小质因子左乘 i 的方式得到的合数
if(i % primes[j] == 0) break;
// 出现 i 是 primes[j] 的倍数情况时,
// primes[j] 后一个质数左乘 i 就不是 "最小质因子左乘的方式" 了,
// 如 i = 4, primes[j] = 2, primes[j] 后一个质数是 3,
// 3 * 4 显然不是 "最小质因子左乘的方式", 而应该是 2 * 6
}
}
}
代码：
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int n;
void get_divisors(int n)
{
vector<int> res;
for (int i = 1; i <= n / i; i++) {
if (n % i == 0) {
res.push_back(i);
if (i != n / i) { // 避免 i==n/i, 重复放入 （n是完全平方数
res.push_back(n / i);
}
}
}
sort(res.begin(), res.end());
for (auto item : res) {
cout << item << " ";
}
puts("");
}
int main()
{
cin >> n;
while (n--) {
int x;
cin >> x;
get_divisors(x);
}
return 0;
}
基于算数基本定理
#include<iostream>
#include<algorithm>
#include<unordered_map>//哈希表
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main()
{
int n;
cin>>n;
unordered_map<int,int> primes;//存储所有的底数和指数
while(n--)
{
int x;
cin >> x;
for(int i = 2;i <= x / i;i++)
{
while(x % i == 0)
{
x /= i;
primes[i]++;//指数累加
}
}
if(x > 1) primes[x] ++;
}
LL res = 1;
for(auto prime : primes) res = res * (prime.second + 1) % mod;
cout<<res<<endl;
return 0;
}
while (b -- ) t = (t * a + 1) % mod;
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int main()
{
int n;
cin >> n;
unordered_map<int, int> primes;
while (n -- )
{
int x;
cin >> x;
for (int i = 2; i <= x / i; i ++ )
while (x % i == 0)
{
x /= i;
primes[i] ++ ;
}
if (x > 1) primes[x] ++ ;
}
LL res = 1;
for (auto p : primes)
{
LL a = p.first, b = p.second;
LL t = 1;
while (b -- ) t = (t * a + 1) % mod;
res = res * t % mod;
}
cout << res << endl;
return 0;
}
解法一：直接用辗转相除法求解
#include<bits/stdc++.h>
using namespace std;
int n,a,b;
//选其一即可
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
/*int gcd(int x,int y){
if(x % y == 0)return y;
return gcd(y,x % y);
}*/
int main() {
cin >> n;
while(n--){
cin >> a >> b;
cout << gcd(a,b) << endl;
}
return 0;
}
解法2：使用STL中的__gcd函数
（注意！函数前面有两个下划线哦。即：是“__gcd”而不是“_gcd”）
库函数
#include<algorithm>
#include<bits/stdc++.h>//万能头文件
using namespace std;//这句话一定不能忘哦！
int n,a,b;
int main() {
cin >> n;
while(n--){
cin >> a >> b;
cout << __gcd(a,b) << endl;//调用STL函数
}
return 0;
}