#include<stdio.h>
#define num 10000000
int a[10000009]={0};

void sieve()
{
     int i,j;
       for(i=2;i<=3164;i++)          //loop till sqrt of largest number 10^7     
       {
              if(a[i]==0)                  // all primes are marked 0
              {
                   for(j=i*i;j<=num;j+=i)
                   {
                           if(a[j]==0)             
                            a[j]=i;        // if i is prime then all it's multiples pos have value of i   
                   }
              }
       }

       return;      // a[] is storing each nummber's smallest prime number which can divide it
}

int main()
{
     int n=0;
     a[1]=0;
     sieve();

     while(scanf("%d",&n)!=EOF)
     {
            printf("1");

            if(n==1)
            {
                printf("\n");
                continue;    
            }

            int k=n;

            while(a[k]!=0)                    // while it doesnt reach a prime number
            {
                printf(" x %d",a[k]);   
                k/=a[k];
            }
            printf(" x %d",k);               //print that prime number

            printf("\n");
     }    

     return 0;
}

hello, this is a code to print the factorization of a number upto 10^7 efficiently than brute force(much).So i want to optimize it more further. any one can make it more optimize so as to run it in better time ? thanks

I did this as a self-teaching exercise about 27 years ago.

  1. Create a static array of primes up to 10,000 using the Sieve of Aristhostenes.
  2. Utilize a RECURSIVE, binary partitioning algorithm to determin if a number is prime.

First, find the largest prime number <= 1/2 of the new number (or old one if it is not even) and see if that is a factor. If so, the results of dividing the source by the prime is your new number.
Second, keep going back to the Second step until you can't any longer.

Using this algorithm, I was able to factorize any number into primes up to the biggest integer value supported by a 64-bit floating point number. If I was ambitions, I would have used an 80-bit integer value in the 8087 math co-processor I had in my computer at the time. It was VERY fast. A number up to 10^7 would take well under 30 discrete computations!

The original C source code resides on archived floppy discs in my home office, but finding it would take more time than I can allocate right now!

Edited 4 Years Ago by rubberman

For full factorization sieve you can store the smallest prime factor for each number and then you have all numbers factored only by traversing through the sieve.

Edited 4 Years Ago by pyTony

This article has been dead for over six months. Start a new discussion instead.