文章目录
数学知识
数学真是一个令人摸不着头脑的一个东西，小小的质数都可以把你拿捏得死死的
一、质数
1、试除法判定质数
朴素做法（容易超时，时间复杂度O(n)）
#include <iostream>
using namespace std;
int check_primes(int x)
{
if(x==1)
return 0;
for (int i = 2; i < x; i++)
{
if (x % i == 0)
return 0;
}
return 1;
}
int main()
{
int n;
cin >> n;
while (n--)
{
int a;
cin >> a;
if (check_primes(a))
cout << "Yes"<<endl;
else
cout << "No"<<endl;
}
return 0;
}
2、开方判定质数
因为一个数n可以分为两个数的乘积，一个比n的开平方根小，另一个比开平方大，所以遍历到sqrt（n）即可（O(sqrt(n))）
#include <iostream>
using namespace std;
int check_primes(int x)
{
if(x==1)
return 0;
for (int i = 2; i <= x/i; i++)
{
if (x % i == 0)
return 0;
}
return 1;
}
int main()
{
int n;
cin >> n;
while (n--)
{
int a;
cin >> a;
if (check_primes(a))
cout << "Yes"<<endl;
else
cout << "No"<<endl;
}
return 0;
}
3、分解质因数
给定 n个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
#include <iostream>
#include <algorithm>
using namespace std;
void divide(int x)
{
for (int i = 2; i <= x / i; i++)
{
if (x % i == 0)
{
int s = 0;
while (x % i == 0)
{
x /= i;
s++;
}
printf("%d %d\n", i, s);
}
}
if (x > 1)
{
printf("%d 1\n", x);
}
printf("\n");
}
int main()
{
int n;
cin >> n;
while (n--)
{
int a;
cin >>a;
divide(a);
}
return 0;
}
4、筛质数
1~n中有n/lnn个质数
(1)、埃氏筛法
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
int st[N], primes[N],cnt;
void get_primes(int x)
{
for (int i = 2; i <= x; i++)
{
if (!st[i])
primes[cnt++] = i;
for (int j = i + i; j <= x; j += i)
{
st[j] = 1;
}
}
printf("%d", cnt);
}
int main()
{
int n;
cin >> n;
get_primes(n);
return 0;
}
(2)、线性筛
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
int st[N], primes[N], cnt;
void get_primes(int x)
{
for (int i = 2; i <= x; i++)
{
if (!st[i])
primes[cnt++] = i;
for (int j = 0; primes[j] <= x/i; j++)
{
st[i * primes[j]] = 1;
if (i % primes[j] == 0)
break;
}
}
printf("%d", cnt);
}
int main()
{
int n;
cin >> n;
get_primes(n);
return 0;
}
二、约数
1、试除法求约数
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
vector<int> res;
for (int i = 1; i <= n / i; i++)
{
if (n % i == 0)
{
res.push_back(i);
if (n / i != i)
res.push_back(n / i);
}
}
sort(res.begin(), res.end());
for (auto x : res) cout << x << " ";
cout << endl;
}
}
2、约数个数
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int mod = 1e9 + 7;
int main()
{
int t;
cin >> t;
unordered_map<int, int> h;//无序map集合存储质因数和质因数对应的出现的最大次数
while (t--)
{
int n;
cin >> n;
for (int i = 2; i <= n / i; i++)
{
while (n % i == 0)
{
h[i]++;
n /= i;
}
}
if (n > 1)h[n]++;
}
long long res = 1;
for (auto iter = h.begin(); iter != h.end(); iter++)
{
res = res * (iter->second + 1) %mod;
}
cout << res;
return 0;
}
总结
还在持续更新中
标签：return,int,质数,cin,笔记,数学知识,primes,include,acwing From： https://blog.csdn.net/llllllllllllkllk/article/details/140571095