循環式質數 (c/c++)

//===============================================================
// 20090521 知識 +
// http://tw.knowledge.yahoo.com/question/question?qid=1009052111388
// 發問者 :(兔〞ｍａｎ〃 ) http://tw.knowledge.yahoo.com/my/my?show=AB01282140
//===============================================================

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

const int _max = 100000;    // 質數表大小
int prime[_max] = { 2, 3, 5, 7, 11 };
int _lx;
// --- 建立質數表
void initPrime()
{
  int p, x=4, i=5;
  for(int n=13; i<_max; n+=x, x=6-x)
  {
     int q = (int)sqrt((double)n);
     for(p=1; p<i && prime[p]<=q; p++)
        if (n%prime[p]==0) p=i;
     if (p<i) prime[i++] = n;
  }
  _lx = 6-x;
  return;
}
// --- 檢查是否為質數
bool IsPrime(long long num)
{
  int i = (int)(num%6);
  if (num>6 && i!=1 && i!=5) return false;
  long q = (long) sqrt((long double)num);
  for(i=2; i<_max && prime[i]<=q; i++)
     if (num%prime[i]==0) return false;
  if (i<_max) return true;
  long n = prime[_max-1]+_lx;
  for(i=_lx ;n<=q; n+=i, i=6-i)
     if (num%n==0) return false;
  return true;
}
// --- 指定位數的循環式質數檢查
char d[4] = { 1, 3, 7, 9 };
char a[16];
void checkN(int n)
{
  printf( "\n %d 位數:", n );
  int i, m, c, l, o=1, max = 1;
  for(i=0; i<n; i++) { max*=4; o*=10; }
  for(l=0, o/=10; l<max; l++)
  {
     for(i=n-1, m=l; i>=0; i--, m/=4) a[i]=d[m%4];
     for(i=0, c=0; i<n; i++) c=c*10+a[i];
     for(i=0, m=c; i<n; i++, m=m/10+m%10*o)
        if (!IsPrime(m)) break;
     if (i==n) printf( " %d", c );
  }
  printf("\n");
}
// --- 檢查是否為循環式質數
bool checkNum(int c)
{
  int m, n, o, i;
  for(m=c, n=0; m>0; m/=10) n++;   // 計算位數
  // if (n<2 || n>8 ) return false;
  for(i=1, o=1; i<n; i++) o*=10;   // 偏移值
  for(i=0, m=c; i<n; i++, m=m/10+m%10*o)  //循環
     if (!IsPrime(m)) return false;
  return true;
}
// =========== 主程式 ============
int main()
{
  clock_t start = clock();
  initPrime();
  clock_t begin = clock();
  printf( "\n循環式質數 總覽 -- \n");
  for(int nn=2; nn<9; nn++) checkN(nn);
  clock_t end = clock();
  printf( "\n總計時間: %.3fsec.  質數表建立時間: %.3fsec.  處理時間: %.3fsec.\n\n",
          (double)(end-start)/CLOCKS_PER_SEC, (double)(end-begin)/CLOCKS_PER_SEC,
          (double)(begin-start)/CLOCKS_PER_SEC );
  //------------
  int d;
  while(1)
  {
     printf("\n請輸入一個2~9位數值, 將檢測其是否為循環式質數 :");
     if (scanf("%d", &d)!=1 || d<10 || d>999999999) break;
     if (checkNum(d)) printf("○ %d是一個循環式質數!!\n", d);
     else  printf("╳ %d不是一個循環式質數!!\n", d);
  }
  return 0;
}
//====================================================