Sunday, September 18, 2011

Prime factor resolve on C

 Author:Yangs
Maximum number is in favor of 4294967294, i.e. scanf("%lu") can go to maximum number.

Because resolve 4294967294 only to need prime table of 65535, Speed is more quickly.

In theory, 2.5×10^17 is resolved both short time. 2.5×10^17 need prime table of 500000000, My computer need 12.015 s

Code:
/**

 *   N*30+1, N*30+7, N*30+11, N*30+13, N*30+17, N*30+19, N*30+23, N*30+29

**/

#include "stdio.h"
#include "math.h"

long unsigned NUM;

char* real;;

long unsigned k;


inline void wtable(register unsigned long a)
{
    register unsigned long b;
    b=a/30;
    a=a%30;
    switch(a)
    {
      case 1:real[b]=real[b]&&!1;break;
      case 7:real[b]=real[b]&&!(1<<1);break;
      case 11:real[b]=real[b]&&!(1<<2);break;
      case 13:real[b]=real[b]&&!(1<<3);break;
      case 17:real[b]=real[b]&&!(1<<4);break;
      case 19:real[b]=real[b]&&!(1<<5);break;
      case 23:real[b]=real[b]&&!(1<<6);break;
      case 29:real[b]=real[b]&&!(1<<7);
      default:;
    }
}

inline int rtable(register unsigned long a)
{
  register unsigned long b;
  if(a>5)
  {
    b=a/30;
    if(real[b]==0)return 0;
    a=a%30;
    switch(a)
    {
      case 1:return real[b]&&1;
      case 7:return real[b]&&(1<<1);
      case 11:return real[b]&&(1<<2);
      case 13:return real[b]&&(1<<3);
      case 17:return real[b]&&(1<<4);
      case 19:return real[b]&&(1<<5);
      case 23:return real[b]&&(1<<6);
      case 29:return real[b]&&(1<<7);
      default:return 0;
    }
  }
  else
  {
    switch(a)
    {
      case 2:return 1;
      case 3:return 1;
      case 5:return 1;
      default:return 0;
    }
  }
}

void suShu()
{


  register unsigned long i=3,j,step;

  for(j=0; j<NUM/30+1; j++)
  {
    real[j] = 0xFF;//初始化数组
  }

  while(i<=k)
  {
  if(rtable(i)==0)
    {
      step=i<<1;
      for(j=i*i;j<=NUM;j+=step)
      wtable(j);
    }
    ++i;
    ++i;
  }

}


int main()
{
  unsigned long in;
  register unsigned long i;
  int f=0;
  printf("please inpout the No.:\n");
  scanf("%lu",&in);
  NUM=(unsigned long)sqrt((long double)in);
  real = new char[NUM/30+1];
  k = (long)sqrt((double)NUM);
  suShu();
  printf("%lu=",in);
  for (i=2;i<=NUM;i++)
  {
    if(rtable(i)==0)
      continue;
    else
    {
      if(in%i!=0)
        continue;
      else
      {
        in=in/i;
        i--;
        printf("%ld*",i+1);
        f=1;
      }
    }

  }
  if(in==1&f==1)printf("\b");
  else if(f==1)printf("%ld",in);
  else if(in<2)printf("\b can not factorization !");
  else printf("\b is prime number !");

  return 0;
}

No comments:

Post a Comment