[原创]判断素数的
#include <stdio.h>#include <math.h>
// 如果是素数返回1,否返回0
int isPrime(int number)
{
int i ,
nSqrt ;
// 素数大于0
if (number <= 1)
{
return 0 ;
}
// 2和3是素数,直接返回,因为数太小,不能用6n筛子
if (number == 2 || number == 3)
{
return 1 ;
}
// 素数都分布在6n+1和6n-1附近,否则不是素数,符号的话也不一定是素数
// 比如5(6*1-1)、 7(6*1+1)、11(6*2-1)、13(6*2+1)。。。。。
if ((number + 1) % 6 == 0 || (number - 1) %6 == 0)
{
// 如果符合6n筛子的话,可以再用传统的方法,如果素数量大的话也可以自己
// 弄一个素数表,提高效率,因为用for,有些数会重复给除,比如一个数,不能
// 给2整除,肯定也不能给4和8整除
nSqrt = sqrt(number) ;
for (i = 2; i <= nSqrt; ++i)
{
if (number % i == 0)
{
return 0 ;
}
}
if (i >= nSqrt)
{
return 1 ;
}
}
return 0;
}
int main(void)
{
int n ;
//scanf("%d", &n) ;
//printf("%s\r\n",isPrime(n)?"是素数!":"不是素数!") ;
while (scanf("%d", &n) > 0)
{
printf("%6d %.10s\r\n",n, isPrime(n)?"是素数!":"不是素数!") ;
}
return 0;
}
页:
[1]