[原创]判断素数的

evilknight

#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;
}