判断素数的方法
判断素数的方法有三种,常规法,埃式筛法,欧拉筛法。
1.常规方法
void normal(int m)
{
bool is = 0;
if(m==1||m==0)
{
cout << m << "不是素数";
}
else{
for (int i = 2; i <= sqrt(m);i++)
{
if(m%i==0)
{
is = 1;
break;
}
}
}
if(is==0)
cout << m << "是素数";
else
cout << m << "不是素数";
}
2.埃式筛法(O(nlogn))
void Ais(int m)////埃式筛法
{
memset(prime, 0, sizeof(prime));
memset(vis, 0, sizeof(vis));
prime[0] = prime[1] = 1;
for (int i = 2; i <= m;i++)
{
if(!prime[i])
{
for (int j = i * 2; j <= m;j+=i)
{
prime[j] = 1;
}
}
}
}
3.欧拉筛法(O(n))
void OLA(int m)//欧拉筛法
{
int ans = 0;
memset(prime, 0, sizeof(prime));
memset(vis, 0, sizeof(vis));
for (int i = 2; i <= m; i++)
{
if(!vis[i])
{
prime[ans++] = i;
}
for (int j = 0; j < ans;j++)
{
if(i*prime[j]>m)
break;
vis[i * prime[j]] = 1;
if(i%prime[j]==0)
break;
}
}
}
原文链接: https://www.cnblogs.com/a821403286/p/13693386.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/202947
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!