Display a number as a product of its prime factors

Question

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 <= N <= 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 <bits/stdc++.h>
using namespace std;
vector<long long>Primes(1e7);
bool prime(long long x)
{

    for(int i=2;i<=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<=1e7;i++)
                    {
                            if(Primes[i]==0)
                            {
                               Primes[i]=i;
                               for(int j=2;i*j<=1e7;j++)
                                {
                                    if(Primes[i*j]==0)
                                    Primes[i*j]=i;
                                }

                             }
                    }

 }
vector<long long>factorise(int x)  //This is to store the factors 
                                   //of a number 

{
    vector<long long>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", &n) == 1)
if(n==1)
{
    cout<<"1"<<endl;
}
else{

    vector<long long>ans=factorise(n);
    cout << "1 x" ;
    for(int i=0;i<ans.size();i++)
    {
        if(i==ans.size()-1)
            printf(" %d ", ans[i]);
        else
            printf(" %d x", ans[i]);
    }
    cout<<endl;
}
    return 0;
}

Answer 1

Don't include <bits/stdc++.h> - 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 < Primes.size();  i += 2) {
        Primes[i] = 2;
    }

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

        Primes[i] = i;
        for (std::size_t j = i * i;  j < 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.

Answer 2

I'll add :

• Why not using your vector in your prime(...) function?
• Using std::endl sending a '\n' and then flushes the output buffer. So std::endl is more expensive in performance.
• Since least_prime_factor can be computed at compile time, maybe try to make it constexpr (plus use an std::array for Primes).
• You mix out outputting functions from <iostream> (std::cout) and from <cstdio> (printf(...)); try to be coherent.
• Instead of printing "1 x " (and then conditionally "N x " for each value, or " N" if it's the last), just print "1" (and then, unconditionally print " x N" for each)
• You can print result directly from factorise instead of ret.push_back(Primes[x]);, so you avoid returning a vector by value and iterate over it.
• Don't mix types, neither in comparison operations nor in arithmetic operations. Here, you have long long, int, double (as the result of sqrt(..), but also with 1e7) and unsigned int (vector::size() return a vector::size_type which is an unsigned int). Mixing signed and unsigned, integer and floating point, in arithmetic or comparison is a very bad idea.

And, yeah, try to space your code, it'll help readability.

note: I fixed indent in your code for a more readable, but it seems you rejected :/

Answer 3

First of all you are using cout and asking for TLE help !!!. You need to remove cout first from your code Also i can see that you use local vector array assignment in our main function. Local vector allocation is time consuming. Try to avoid this too.