任何一个自然数,总可以表示成如下形式之一:
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;
}