Search This Blog

Loading...

Write a program to Calculate Prime Factor of a Number



//Write a program to calculate prime factor of a number
#include<stdio.h>
#include<math.h>
#define SIZE_N 100000
#define SIZE_P 66457


bool flag [SIZE_N] ;
int prime [SIZE_P] ;


void seive ()
{
 int i,j,r,c=0,p ;
 for (i=3;i<=SIZE_N;i+=2)  flag[i] = true;


 flag[2]=true;
 prime[c++]=2;
 p=SIZE_N+1;
 for(i=3;i<p;i+=2)
 {
        if ( flag[i] )
        {
            prime[c++]=i;
            if ( SIZE_N / i >= i )
            {
                r=i*2;
                for(j=i*i;j<p;j+=r) flag[j]=false;
            }
        }
 }
}
int prime_factor(long num)
{
     int i=0;
 if(num<0)
 {
  printf("-1 x ");
  num*=-1;
 }
     long base=(long)(sqrt(num)+0.005);
     while(prime[i]<=base&&num>1)
     {
  if (num%prime[i]==0)
  {
   num /= prime[i];
   if(num!=1) printf("%ld x ",prime[i]);//store here factor
   else       printf("%ld",prime[i]);// store here factor
  }
  else i++;
 }
     if(num>1) printf("%ld",num);
     return i;
}


int main()
{
     long num;
 seive();
     while(scanf("%ld",&num) == 1 && num )
     {
  printf("%ld = ",num);
  prime_factor(num);
  printf("\n");
     }
}

/*
Input:6 12 20
Output:2x3,2x2x3,2x2x5
*/

No comments:

Post a Comment