当前位置: 代码迷 >> 综合 >> 【Eternallyc】素数6N+1法
  详细解决方案

【Eternallyc】素数6N+1法

热度:75   发布时间:2023-12-26 01:01:56.0

任何一个自然数,总可以表示成如下形式之一:
6N,6N+1,6N+2,6N+3,6N+4,6N+5(N=0,1,2,…..)
当N>=1时,只有6N+1和6N+5的自然数有可能是素数。

除了2和3之外,所有的素数都可以表示成6N+1的形式(N为自然数)

#include <cstdio>
bool Isprime(int n)
{if(n==2)return true;if(n%2==0)return false;for(int a = 3;a *a <=n;a +=2){if(!(n%a))return false;}return true;
}
int main()
{int n;for(int a = 2;a < 100;a ++){if(Isprime(a))printf("%d ",a);}return 0;
}