prime factorization optimization

[nitin1]

#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

[rubberman]

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!

[TrustyTony]

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.