数学
作者:
骏杰
,
2022-05-10 22:07:18
,
所有人可见
,
阅读 146
试除法判断质数:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
bool is_prime(int n)
{
if(n<2) return false;
for(int i=2;i<=n/i;i++)
{
if(n%i==0)
return false;
}
return true;;
}
int main()
{
scanf("%d",&n);
while(n--)
{
int a;
scanf("%d",&a);
if(is_prime(a)) puts("Yes");
else puts("No");
}
return 0;
}
分解质因数:
样例:
2//2行
6
8
2 1
3 1
2 3
代码:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void divide(int n)
{
for(int i=2;i<=n/i;i++)
{
if(n%i==0)
{
int s=0;
while(n%i==0)
{
n/=i;
s++;
}
printf("%d %d\n",i,s);
}
}
if(n>1) printf("%d %d\n",n,1);
puts("");
}
int main()
{
int x;
scanf("%d",&x);
while(x--)
{
int n;
scanf("%d",&n);
divide(n);
}
return 0;
}
筛质数:
求质数个数
原理:
例如:2,3,4,5,6,7,8,9,10,11,12,13
(删去质数的倍数)删去2的倍数,3的倍数,5的倍数,7的倍数,11的倍数,剩下的都是质数
#include <iostream>
#include <algorithm>
using namespace std;
const int N= 1000010;
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;
for(int j = 0; primes[j]<=n/i;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
int main()
{
int n;
cin>>n;
get_primes(n);
cout<<cnt<<endl;
return 0;
}
试除法求约数:
//6:1,2,3,6
//8:1,2,4,8
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int>get(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) res.push_back(n/i);//把不同的约数加进去
}
}
sort(res.begin(),res.end());
return res;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int x;
scanf("%d",&x);
auto sum=get(x);//vector..
for(auto i:sum)
{
cout<<i<<" ";
}
cout<<endl;
}
return 0;
}