evilknight 发表于 2009-7-28 21:31:11

[原创]判断素数的

#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]
查看完整版本: [原创]判断素数的