判断质数
枚举前根号n个数若没有约数则是质数
void solve()
{
int n;
cin>>n;
if(n<2)
{
cout<<"No"<<endl;
return;
}
else
{
for(int i=2;i<=n/i;i++)
{
if(n%i==0)
{
cout<<"No"<<endl;
return;
}
}
}
cout<<"Yes"<<endl;
}
分解质因数
根据算法基本定理 N=p1^a1p2^a2pn^an
则一定存在一个<根号n的只因子,还有可能存在>根号n的因子需要特判
void solve()
{
int n;
cin>>n;
for(int i=2;i<=n/i;i++)
{
int cnt=0;
if(n%i==0)
{
while(n%i==0) cnt++,n/=i;
cout<<i<<' '<<cnt<<endl;
}
}
if(n>1) cout<<n<<' '<<'1'<<endl;
cout<<endl;
}
晒质数
朴素晒法
void solve()
{
int n;
cin>>n;
for(int i=2;i<=n;i++)
{
if(!st[i])
{
arr.push_back(i);
}
for(int j=i;j<=n;j+=i)
{
st[j]=true;
}
}
cout<<arr.size()<<endl;
}