试除法判定质数
输入样例
2
2
6
输出样例
Yes
No
代码
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
while (n--)
{
int a, i;
cin >> a;
if (a < 2)
printf("No\n");
else
{
for (i = 2; i <= a / i; i++)//枚举到较小的约数
if (a % i == 0)
break;
if (i > a / i)
printf("Yes\n");
else
printf("No\n");
}
}
return 0;
}
分解质因数
输入样例
2
6
8
输出样例
2 1
3 1
2 3
代码
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
while (n--)
{
int a, i;
cin >> a;
if (a < 2)
printf("1 1\n\n");
else
{
for (i = 2; i <= a / i; i++)
{
int sum = 0;
while (a % i == 0)
{
a /= i;
sum++;
}
if (sum != 0)
printf("%d %d\n", i, sum);
}
if (a > 1)//表示还剩下最大的一个质因数
printf("%d 1\n", a);
}
printf("\n");
}
return 0;
}
试除法求约数
输入样例
2
6
8
输出样例
1 2 3 6
1 2 4 8
代码
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
set<int> divisors(int n)
{
set<int>res;//内部有序,不需要排序
for (int i = 1; i <= n / i; i++)
{
if (n % i == 0)
{
res.insert(i);
if (i != n / i)//判断是否是同一个数
res.insert(n / i);
}
}
return res;
}
int main()
{
int n;
cin >> n;
while (n--)
{
int a, i;
cin >> a;
auto res = divisors(a);
for (auto it : res)
cout << it << ' ';
cout << endl;
}
return 0;
}
约数个数
输入样例
3 //n个数的乘积
2
6
8
输出样例
12
代码
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main()
{
int n;
unordered_map<int, int>prime;
cin >> n;
while (n--)
{
int a;
cin >> a;
for (int i = 2; i <= a / i; i++)
{
while (a % i == 0)
{
a /= i;
prime[i]++;//对应底数的指数加一
}
}
if (a > 1)//表示还剩下最大的一个质因数
prime[a]++;
}
LL res = 1;
for (auto it : prime)
res = res * (it.second + 1) % mod;//约数个数定理
cout << res;
return 0;
}
约数之和
输入样例
3 //n个数的乘积
2
6
8
输出样例
252
代码
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main()
{
int n;
unordered_map<int, int>prime;
cin >> n;
while (n--)
{
int a;
cin >> a;
for (int i = 2; i <= a / i; i++)
{
while (a % i == 0)
{
a /= i;
prime[i]++;//对应底数的指数加一
}
}
if (a > 1)//表示还剩下最大的一个质因数
prime[a]++;
}
LL res = 1;
for (auto it : prime)
{
int p = it.first, z = it.second;
LL t = 1;
while (z--)
t = (t * p + 1) % mod;//秦九韶算法,计算p^0+p^1+...+p^z
res = res * t % mod;//约数和的计算:(p1^0+p1^1+…+p1^z1)∗…∗(pk^0+pk^1+…+pk^zk)
}
cout << res;
return 0;
}