质数
质数:在大于1的整数中,如果只包含1和本身这俩个约束,就被叫质数或素数。
质数判定试除法
质数的判定——试除法:如果d能整除n,则n/d再除n,结果是一个整数。 d≤n/d。
![第四章——数学知识1](https://imgs.yssmx.com/Uploads/2023/04/425955-1.png)
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
分解质因数试除法
质因数:一个正整数的俩个因数都是质数
分解质因数——试除法:
![第四章——数学知识1](https://imgs.yssmx.com/Uploads/2023/04/425955-2.png)
从小到大枚举所有的质因数,这里我们要的是质因子,即因子是质数。
当枚举到i时,不包含任何2到i-1中的质因子
![第四章——数学知识1](https://imgs.yssmx.com/Uploads/2023/04/425955-3.png)
如果n% i==0,则说明n中不包含任何2到i-1之间的质因子,i当中也不包含任何2到i-1中的质因子
,因此i一定是一个质数。
即只要满足if(n%i==0)说明i一定是质数。n中最多只包含一个大于sqrt(n)的质因子(假设n中有俩个大于sqrt(n)的质因子,俩俩乘一块之后肯定大于n),因此枚举的时候可以先把小于根号n的枚举出来,如果最后剩余的数大于1,则说明这个数时大于根号n的质因子
![第四章——数学知识1](https://imgs.yssmx.com/Uploads/2023/04/425955-4.png)
![第四章——数学知识1](https://imgs.yssmx.com/Uploads/2023/04/425955-5.png)
void Prime(int n)//求质因数
{
int count = 0;
for (int i = 2; i <= n/i; ++i)
{
count = 0;
if (n % i == 0)// i是质数
while (n % i == 0)
{
n = n / i;//n变成另一个因数,如n原来是6,i是3,n此刻变为2
count++;//如果要把一个数表示成指数和底数的形式,如8=2^3,count就是指数,i就是底数
}
printf("%d %d\n", i, count);
}
if (n > 1) printf("%d 1\n", n);//大于根号n的质数
}
int main()
{
while (1)
{
int n;
scanf("%d", &n);
Prime(n);
}
return 0;
}
筛质数
把一个数组里面,所有数的倍数删掉。
如这里第一个数是2,先把2的所有倍数删掉,接着删除3的所有倍数,删4的所有倍数……
![第四章——数学知识1](https://imgs.yssmx.com/Uploads/2023/04/425955-6.png)
如果某个数没有被筛过的话,说明它是一个质数、
上面算法较为麻烦,我们可这样做,以11为例,我们不需要把2-10的所有数都进行判断,我们把2-10中的质数找出来,看11是不是这些质数的倍数,如果不是则说明11是质数,反之不是质数。即:筛的时候把质数的所有倍数筛出来即可。
![第四章——数学知识1](https://imgs.yssmx.com/Uploads/2023/04/425955-7.png)
方法一 埃氏筛法
时间复杂度 O(nloglogn)
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, cnt;
int prime[N];//用来存储质数
bool st[N];//st代表是否被删除,true代表被删除,false代表未删除
void primes()
{
for (int i = 2; i <= n; i++)
{
if (!st[i])prime[cnt++] = i;//如果当前数没有被筛出去,说明是质数
for (int j = i + i; j <= n; j += i)//把每个数的倍数删掉
{
st[j] = true;
}
}
}
int main()
{
cin>>n;
primes();
cout<<cnt<<endl;
return 0;
}
方法二 线性筛法
合数:合数是指在大于1的整数中除了能被1和本身整除外,还能被其他数(0除外)整除的数
这里争取用合数的某个质因子把每个合数筛掉,线性筛法要优于第一种筛法。
using namespace std;
const int N = 1000010;
int n, cnt;
int prime[N];//用来存储质数
bool st[N];//st代表是否被删除,true代表被删除,false代表未删除
void primes()
{
for (int i = 2; i <= n; i++)
{
if (!st[i])prime[cnt++] = i;//如果当前数没有被筛出去,说明是质数
for (int j = 0; prime[j] <= n / i; j++)//从小到大枚举所有的质数,当质数大于某个数的平方根时,跳出循环
{
st[prime[j] * i] = true;//把primes[j]*i筛掉
if (i % prime[j] == 0) break;
}
}
}
int main()
{
cin >> n;
primes();
cout << cnt << endl;
return 0;
}
线性筛法核心:n只会被它的最小质因子筛掉。
原理:j时从小到大在枚举所有的质数。下面图中的pj代表prime[j]
![第四章——数学知识1](https://imgs.yssmx.com/Uploads/2023/04/425955-8.png)
试除法求约数
如果d是n的约数,则n/d也一定能整除n,即我们枚举约数时,枚举到d≤n/d即d≤根号n
![第四章——数学知识1](https://imgs.yssmx.com/Uploads/2023/04/425955-9.png)
#include<vector>
vector<int> get_divisors(int n)
{
vector<int> res;
for(int i=1;i<=n;++i)
if (n % i == 0)
{
res.push_back(i);//如果i是约数,就把i放入到数组中
if (i != n / i) res.push_back(n/i); //当i不等于n/i时,再把n/i放进来,有可能n是i的平方,如果俩个约数一样,数组里面放的约数可能会重复
//所以这里要判断一下
}
sort(res.begin(), res.end());
return res;
}
int main()
{
int n;
cin >> n;
while (n--)
{
int x;
cin >> x;
auto res = get_divisors(x);
for (auto x : res)
cout << x << " ";
cout << endl;
}
return 0;
}
约数个数和约数之和
约数个数:如果一个正整数N分解完质因数后可这样表示
![第四章——数学知识1](https://imgs.yssmx.com/Uploads/2023/04/425955-10.png)
则它的约数个数可表示为
![第四章——数学知识1](https://imgs.yssmx.com/Uploads/2023/04/425955-11.png)
1~n中1是所有数的约数,2是所有以2为倍数的约数……,因此1-n当中总共约数的个数和1-n当中
总共倍数的个数是相同的, 因此我们可以通过统计1-n当中有多少倍数,进而统计出约数。
int范围内约数个数最多的大概是1500个。
约数之和:可这样表示
![第四章——数学知识1](https://imgs.yssmx.com/Uploads/2023/04/425955-12.png)
![第四章——数学知识1](https://imgs.yssmx.com/Uploads/2023/04/425955-13.png)
解题思路:把a1-an分解成这种形式,之后所有指数+1再相乘
![第四章——数学知识1](https://imgs.yssmx.com/Uploads/2023/04/425955-14.png)
#include<unordered_map>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int n;
int main()
{
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]++;//质因数指数+1
}
}
if (x > 1) primes[x]++;//如果x>1说明x是一个比较大的质因数
}
LL res = 1;
for (auto prime : primes)
res = res * (prime.second + 1) % mod;
cout << res << endl;
return 0;
}
求约数和
先求出p的0次方一直加到p的a次方,用这个公式t会由t变为p的1次方,一直乘下去会变为t的a次方文章来源:https://www.toymoban.com/news/detail-425955.html
![第四章——数学知识1](https://imgs.yssmx.com/Uploads/2023/04/425955-15.png)
![第四章——数学知识1](https://imgs.yssmx.com/Uploads/2023/04/425955-16.png)
#include<unordered_map>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int n;
int main()
{
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]++;//质因数指数+1
}
}
if (x > 1) primes[x]++;//如果x>1说明x是一个比较大的质因数
}
LL res = 1;
for (auto prime : primes)
{
int p = prime.first, a = prime.second;//p表示底数,a表示指数
LL t = 1;
//求p的0次方加和一直到p的a次方
while (a--)
{
t = (t * p + 1) % mod;
}
res = res * t % mod;
}
cout << res << endl;
return 0;
}
最大公约数(欧几里得算法)
辗转相除法:一个数能整除a,也能整除b,这个数就能整除a+b,也能整除ax+by,求a和b的最大公约数等于求b和a%b的最大公约数,文章来源地址https://www.toymoban.com/news/detail-425955.html
#include<iostream>
using namespace std;
int gcb(int a, int b)
{
return b ? gcb(b, a % b) : a;//b如果不是0,返回gcb(b, a % b),反之返回a
}
int main()
{
int n;
scanf("%d", &n);
while (n--)
{
int a, b;
scanf("%d %d", &a, &b);
printf("%d", gcb(a, b));
}
return 0;
}
到了这里,关于第四章——数学知识1的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!