Display a number as a product of its prime factors Task:

Link to original problem :https://www.spoj.com/problems/FACTCG2/


  The task in this problem is to write a number in a multiplication of
  prime 
      numbers separated by “x”. You need to put the number 1 in this multiplication.
  
  Input:
  
  The input consists of several lines.
  
  Each line consists of one integer N (1 &lt;= N &lt;= 10^7) .
  
  Example Input:

           1
           2
           4
           8 

  
  Example Ouput:

           1
           1 x 2
           1 x 2 x 2
           1 x 2 x 2 x 2



My approach:

I pre-compute an array Primes which contains the smallest prime factor of every number from 1 to 1e7 using the sieve.  Then to find the answer , I divide the number given in each query by its least prime factor until it becomes '1' or a prime number. Then I display it.

The code works for small inputs but SPOJ gives me time limit exceeded. I think maybe the vector in factorise function has 
            something to do with it. I tried printing the answer without storing it in vector but 'x' makes it difficult .

My code:

#include &lt;bits/stdc++.h&gt;
using namespace std;
vector&lt;long long&gt;Primes(1e7);
bool prime(long long x)
{

    for(int i=2;i&lt;=sqrt(x);i++)
    {
        if(x%i==0)
        return false;
    }
    return true;
}
void least_prime_factor()   //To store least prime factor of a 
                             //  given number
 {

    Primes[1]=1;
                    for(int i=2;i&lt;=1e7;i++)
                    {
                            if(Primes[i]==0)
                            {
                               Primes[i]=i;
                               for(int j=2;i*j&lt;=1e7;j++)
                                {
                                    if(Primes[i*j]==0)
                                    Primes[i*j]=i;
                                }

                             }
                    }

 }
vector&lt;long long&gt;factorise(int x)  //This is to store the factors 
                                   //of a number 

{
    vector&lt;long long&gt;ret;
    while(x!=1||prime(x)!=true)
    {
        ret.push_back(Primes[x]);
        x=x/Primes[x];
    }
return ret;
}

int main() {


least_prime_factor();
int n;
while(scanf("%d", &amp;n) == 1)
if(n==1)
{
    cout&lt;&lt;"1"&lt;&lt;endl;
}
else{

    vector&lt;long long&gt;ans=factorise(n);
    cout &lt;&lt; "1 x" ;
    for(int i=0;i&lt;ans.size();i++)
    {
        if(i==ans.size()-1)
            printf(" %d ", ans[i]);
        else
            printf(" %d x", ans[i]);
    }
    cout&lt;&lt;endl;
}
    return 0;
}
Don't include &lt;bits/stdc++.h&gt; - it's not standard, and on platforms that provide it, it drags in far too much.

Don't using namespace std - this namespace is not designed for wholesale inclusion, and can produce subtle bugs when its names overload your own.

Don't use a floating-point number such as 1e7 when you want a simple integer 10'000'000.

Don't compute std::sqrt(x) every time around the loop - save the value as an integer for faster comparisons.

Use unsigned types for unsigned arithmetic.  Given that inputs (and therefore factors) are no greater than 10⁷, we can get away with std::uint_fast32_t rather than long long.

Although the code claims to use a sieve, every input number is inefficiently tested for primality without reference to the sieve (multiple times, even).

Why use a std::vector rather than std::array for something whose size is constant and known at compile time?  Also, why write the size in two places (which need to be consistent) instead of simply using Primes.size()?  (Also, fix the off-by-one error where we overstep the end of the vector).

I recommend using C++ streams, rather than mixing C buffered I/O and forcing the two libraries to repeatedly flush each other.

Avoid global variables - Primes can be a local static member (perhaps with an immediately-executed lambda expression as initializer).

Why not always include 1 as the first result, rather than have to add that in the printing code?



To dive in to one function in particular, let's pick on least_prime_factor().  Apart from the misleading name, we're doing a lot more work than we need to here.  Every time around the loop, we're multiplying i by j (a good compiler will hoist the three i*j into a single computation, and reuse that), but we could simply be adding i each time.

A standard improvement to naive sieves is to observe that every multiple of a prime p that's less than p² also has smaller factor than p, so once we've marked p, we can jump straight to p² before striding by p thereafter.

Apart from the first pass (which marks even numbers), we can stride by 2 p each time (knowing that we've already marked even numbers).  We can take that further with a wheel of factors, but even this is reducing the work by a factor of two.

Let's see what we have now:

// Create an array populated with the smallest prime factor of each
// number, or 0 for primes (and unity).
void least_prime_factor()
{
    Primes[1]=1;
    // First, mark all the even numbers; this allows us to halve the
    // work for all other primes.
    for (std::size_t i = 2;  i &lt; Primes.size();  i += 2) {
        Primes[i] = 2;
    }

    for (std::size_t i = 3;  i &lt; Primes.size();  ++i) {
        if (Primes[i]) { continue; }

        Primes[i] = i;
        for (std::size_t j = i * i;  j &lt; Primes.size();  j += 2 * i) {
            if (!Primes[j]) {
                Primes[j] = i;
            }
        }
    }
}


That's noticeably less work, and if we also replace prime() with a simple lookup in Primes[], then we'll have a much more efficient program.