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;
}
Primes[]
is populated? \$\endgroup\$