1.判断是不是质数
试除法判定质数
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;
}
给定 n 个正整数 ai,判定每个数是否是质数。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个正整数 ai。
输出格式
共 n 行,其中第 i 行输出第 i 个正整数 ai 是否为质数,是则输出 Yes,否则输出 No。
数据范围
1≤n≤100,
1≤ai≤231−1
输入样例:
2
2
6
输出样例:
Yes
No
#include<bits/stdc++.h>
using namespace std;
bool is_prime(int n)
{
if(n==1) return false;
for(int i=2;i<=n/i;i++)
if(n%i==0)
return false;
return true;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
if(is_prime(x)) puts("Yes");
else puts("No");
}
return 0;
}
求质数的一样作用。
#include<bits/stdc++.h>
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]) continue;
primes[cnt ++ ] = i;
for (int j = i + i; j <= n; j += i)
st[j] = true;
}
}
int main()
{
int n;
cin>>n;
get_primes(n);
for(int i=0;i<cnt;i++)
{
cout<<primes[i]<<" ";
}
return 0;
}
2.求约数
for(int i=1;i<=n/i;i++)
{
if(n%i==0)
{
a[sum++]=i;
if(i!=n/i)
a[sum++]=n/i;
}
}
给定 n 个正整数 ai,对于每个整数 ai,请你按照从小到大的顺序输出它的所有约数。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个整数 ai。
输出格式
输出共 n 行,其中第 i 行输出第 i 个整数 ai 的所有约数。
数据范围
1≤n≤100,
2≤ai≤2×109
输入样例:
2
6
8
输出样例:
1 2 3 6
1 2 4 8
#include<bits/stdc++.h>
using namespace std;
int dfs(int x)
{
int a[100],sum=0;
for(int i=1;i*i<=x;i++)
{
if(x%i==0)
{
a[sum++]=i;
if(i!=x/i)
a[sum++]=x/i;
}
}
sort(a,a+sum);
for(int i=0;i<sum;i++)
printf("%d ",a[i]);
printf("\n");
}
int main()
{
int t;cin>>t;
while(t--)
{
int x;cin>>x;
dfs(x);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main()
{
int x;cin>>x;
while(x--)
{
int n,a[1000],sum=0;
cin>>n;
for(int i=1;i<=n/i;i++)
{
if(n%i==0)
{
a[sum++]=i;
if(i!=n/i)
a[sum++]=n/i;
}
}
sort(a,a+sum);
for(int i=0;i<sum;i++)
printf("%d ",a[i]);
cout<<endl;
}
return 0;
}
求个数
变形
#include<bits/stdc++.h>
using namespace std;
int a[1000];
int main()
{
int x,sum=1,ans=0;cin>>x;
while(x--)
{
int n;cin>>n;
sum*=n;
}
for(int i=1;i<=sum/i;i++)
{
if(sum%i==0)
{
a[ans++]=i;
if(i!=sum/i)
a[ans++]=sum/i;
}
}
cout<<ans<<endl;
return 0;
}
求和
#include<bits/stdc++.h>
using namespace std;
int a[1000];
int main()
{
int x,sum=1,ans=0;cin>>x;
while(x--)
{
int n;cin>>n;
sum*=n;
}
for(int i=1;i<=sum/i;i++)
{
if(sum%i==0)
{
a[ans++]=i;
if(i!=sum/i)
a[ans++]=sum/i;
}
}
int res=0;
for(int i=0;i<ans;i++)
{
res+=a[i];
}
cout<<res<<endl;
return 0;
}
求积
#include<bits/stdc++.h>
using namespace std;
int a[1000];
int main()
{
int x,sum=1,ans=0;cin>>x;
while(x--)
{
int n;cin>>n;
sum*=n;
}
for(int i=1;i<=sum/i;i++)
{
if(sum%i==0)
{
a[ans++]=i;
if(i!=sum/i)
a[ans++]=sum/i;
}
}
int res=1;
for(int i=0;i<ans;i++)
{
res*=a[i];
}
cout<<res<<endl;
return 0;
}
给定 n 对正整数 ai,bi,请你求出每对数的最大公约数。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个整数对 ai,bi。
输出格式
输出共 n 行,每行输出一个整数对的最大公约数。
数据范围
1≤n≤105,
1≤ai,bi≤2×109
输入样例:
2
3 6
4 6
输出样例:
3
2
0和a的最大公约数为a
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int main()
{
int x;cin>>x;
while(x--)
{
int a,b;cin>>a>>b;
int d=gcd(a,b);
cout<<d<<endl;
}
return 0;
}
质因数
#include<iostream>
using namespace std;
bool f(int x)
{
int s=0;
for(int i=2;i*i<=x;i++)
{
if(x%i==0)
while(x%i==0)
{
x/=i;
s++;
}
}
if(x!=1)s++;
if(s==12)return true;
else return false;
}
int main()
{
int ans=0;
for(int i=2333333;i<=23333333;i++)
{
if(f(i))ans++;
}
cout<<ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
void divide(int n)
{
//枚举小于等于 sqrt(n) 的质因子
for(int i=2;i<=n/i;i++)
{
if(n%i==0)
{
int s=0;
while(n%i==0)
{
n/=i;
s++;
}
cout<<i<<' '<<s<<endl;
}
}
//唯一大于 sqrt(n) 的质因子
if(n>1) cout<<n<<' '<<1<<endl;
puts("");
}
int main()
{
int n;
cin>>n;
while(n--)
{
int x;
cin>>x;
divide(x);
}
return 0;
}
作者:不高兴的兽奶
链接:https://www.acwing.com/solution/content/146534/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。