## 583 - Prime Factors

All about problems in Volume V. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

### Re: 583 - Prime Factors

I think that my code it´s fine!!!, but i get WA!!!, can you give me special cases???,,please!!!
Code: Select all
`#include<stdio.h>#include<bitset>#include<vector>#include<map>#define L1 1000009#define L2 1009using namespace std;vector<long long int>primos;map<long long int,long long int>factores;bitset<L1>criba;void generate(){    criba.set();  criba.reset(0);  criba.reset(1);       for(int i=2;i<L2;i++){          if(criba.test(i)){          primos.push_back(i);          for(int j=i+i;j<L1;j+=i){ if(criba.test(j)){criba.reset(j);}}          }       }   }   void factoriza(long long int n){int i=0;   factores.clear();     while(i<primos.size() && primos[i]*primos[i]<=n){       if(n%primos[i]==0){       factores[primos[i]]++;  n=n/primos[i];       }       else i++;     }        if(n>1) factores[n]++;  }int main(){ generate();  long long int n;   map<long long int,long long int>::iterator it;  int flag=0;       while(scanf("%lld",&n)==1 && n!=0){       if(flag>0){ puts("");} flag++; printf("%lld =",n);         int flag=1;  if(n<0){flag=0; n=(-1)*n; }              factoriza(n); int many;       it=factores.begin();              if(flag==0){printf(" -1");}       else{printf(" ");          printf("%lld",it->first);         many=it->second;         while(many>1){many--; printf(" x %lld",it->first); } it++;        }                for(;it!=factores.end();it++){             many=it->second;             while(many>0){many--; printf(" x %lld",it->first); }             }             }       return 0;}`
sir. manuel
New poster

Posts: 18
Joined: Sat Nov 20, 2010 7:44 pm

### Re: 583 - Prime Factors

Your code doesn't print '\n' after the last case..

Remove your code after AC
helloneo
Guru

Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 583 - Prime Factors

jejeje, i was trying to use a sieve, but that was stupid, 2^31 it´s a bg num....so i do this version...but iget WA....why????

Code: Select all
`#include<stdio.h>int main(){    long long int num; long long int i,var;       while(scanf("%lld",&num)==1 && num!=0){ int bandera=1;       printf("%lld =",num); var=num;        if(num<0){         printf(" -1"); num=(-1)*num;        for(long long int i=2;i*i<=num;i++){     while(num%i==0){bandera=0; printf(" x %lld",i); num=num/i; }       if(bandera){bandera=0;}     }}     else{      for(i=2;i*i<=num;i++){      if(num%i==0){bandera=0; printf(" %lld",i); num=num/i; break; }     }                for(;i*i<=num;i++){     while(num%i==0){      if(bandera==1){ printf(" %lld",i); bandera=0;}                     else        printf(" x %lld",i);         num=num/i;      }     }    }   if(num>1){if(bandera==0)             printf(" x %lld",num);  else printf(" %lld",num);  }     puts("");           }return 0;    }`
sir. manuel
New poster

Posts: 18
Joined: Sat Nov 20, 2010 7:44 pm

### Re: 583 - Prime Factors

why still TLE what to do more to get rid from TLE
Code: Select all
`#include<stdio.h>#define MAX 47000int primes[MAX],tot=0;void sieve(){   long int i,j;   for(i=3; i*i<MAX; i+=2)   {      if(primes[i]==0)      {         for(j=i*i; j<=MAX; j+=2*i)            primes[j]=1;      }   }   primes[tot++]=2;   for(i=3; i<=MAX; i+=2)   {      if(primes[i]==0)         primes[tot++]=i;   }}int main(){   sieve();   long n,p,r;   int i,k;   while(scanf("%ld",&n)){      k=0;      if(n==0)         break;      else{         printf("%ld =",n);         if(n<0){            printf(" -1");            k=1;            n*=-1;         }         p=n;         for(i=0;primes[i]*primes[i]<=p;i++){            r=primes[i];            while(n%r==0){               if(k)                  printf(" x");               printf(" ");               printf("%d",r);               n/=r;               k=1;            }         }          if(n!=1){            if(k)               printf(" x");            printf(" ");            printf("%ld",n);         }      }      printf("\n");   }   return 0;}`
arif18
New poster

Posts: 1
Joined: Sat Nov 20, 2010 7:40 pm

### Re: 583 - Prime Factors

scanf may return 0 or -1 on failure. So this line is wrong:
while(scanf("%ld",&n)){

You must check that scanf returns 1 here.
mf
Guru

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

### 583 - Prime Factors WA

I have tested several inputs & got right answer. Then why am I getting WA. Plz someone help. Here is my code:
Code: Select all
`#include<iostream>#include<cmath>using namespace std;#define n 100000int a[n];int pr[50000];int main(){   int i,j;   for(i=0;i<n;i++)      a[i]=0;      a[1]=1;   for(i=2;i<n;i++)   {      if(!a[i])      {         for(j=2;i*j<n;j++)         {            a[i*j]=1;         }      }   }   j=0;int count=0;   for(i=1;i<n;i++)   {      if(a[i]==0)      {         pr[j]=i;         j++;         count++;      }   }   long long int num,temp;   int first=0;   while(scanf("%lld",&num)==1 && num)   {      printf("%lld = ",num);      if(num<0)      {         temp=(-1)*num;         cout<<"-1";         first=1;      }      else         temp=num;      for(i=0;pr[i]<=sqrt(temp) && temp!=1;i++)      {         while(temp%pr[i]==0)         {            if(!first)            {               first=1;            }            else               cout<<" x ";            cout<<pr[i];            temp=temp/pr[i];         }      }      if(temp!=1)      {         if(!first)         {            first=1;         }         else            cout<<" x ";         printf("%lld",temp);      }      cout<<endl;      first=0;   }   if(!num)      cout<<endl;   return 0;}`

It will be very helpful.
slash190
New poster

Posts: 2
Joined: Thu Feb 10, 2011 11:52 am

### Re: 583 - Prime Factors

i don't know why i'm getting TLE ... this is really disappointing
i'm generating primes with Sieve till 50000 then just generate the factors ....
and if there is no factors i print the number itself because it's prime of course ...
i'm sure my logic is right ... can't find what's wrong in my implementation using Java..
Code: Select all
`Accepted!`
New poster

Posts: 16
Joined: Thu Apr 28, 2011 10:48 pm

### Re: 583 - Prime Factors

where is bug in my code:

#include<stdio.h>
#include<math.h>
int prime[5000],k;
int list[5000];
void prime_num()

{
int a=5000;

int sq,i,j,str[5000]= {0};
sq=sqrt(a);
for(i=3; i<=sq; i+=2)
if(str[i]==0)
for(j=i*i; j<=a; j+=2*i)
str[j]=1;
prime[0]=2;
int x=1;
for(i=3; i<=a; i+=2)
if(str[i]==0)
prime[x++]=i;

}

void prime_fator(int n)
{

k=0;
int i;
for(i=0;prime[i]<=n;i++)
if(n%prime[i]==0)
while(n%prime[i]==0)
{
n/=prime[i];
list[k++]=prime[i];
}
}
int main()
{
int i,n;
while(scanf("%d",&n)==1)
{
prime_fator(n);

for(i=0;i<k;i++)
printf("%d ",list[i]);
printf("\n");
}
return 0;
}
sumit saha shawon
New poster

Posts: 19
Joined: Tue Jun 26, 2012 9:19 pm

### Re: 583 - Prime Factors

you're not running prime_num() so prime[] is full of 0's.
brianfry713
Guru

Posts: 1861
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 583 - Prime Factors

I got RE... in this problem.... bt why!!!!!!!! :'( ... here is my code.. i used seive method in here..

#include<stdio.h>
#include <string.h>
#include <math.h>
long long int a[1000000],b[1000000];
long long int seive()
{
long long int i,j,k=0;
memset(a,0,sizeof(a));
a[0]=a[1]=1;
for (i=2;i<1000000;i++)
{
if (a[i]==0)
{
b[k++]=i
;
for (j=i+i;j<1000000;j+=i)
{
a[j]=1;
}
}
}
return 0;
}
int main()
{
long long int n,i,q,x,c;
seive();
while (scanf("%lld",&n)!=EOF)
{
if (n==0)
break;
if (n<0)
{
printf("%lld = -1 * ",n);
c= n*-1;
x=c;
}
else if (n>0)
{
printf("%lld = ",n);
x=n;
}
i=0;
q=0;
while (x!=1)
{
if(x%b[i]==0)
{
x=x/b[i];
if(q==0)
{
printf("%lld",b[i]);
q=1;
}
else
printf(" * %lld",b[i]);
}
else
{
i++;
}
}

i=0;
q=0;
while (x!=1)
{
if(x%b[i]==0)
{
x=x/b[i];
if(q==0)
{
printf("%lld",b[i]);
q=1;
}
else
printf(" * %lld",b[i]);
}
else
{
i++;
}
}
printf("\n");
}
return 0;
}
rifath_csedu
New poster

Posts: 2
Joined: Fri Aug 10, 2012 2:18 pm

### Re: 583 - Prime Factors

Try input 2147483647
brianfry713
Guru

Posts: 1861
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 583 - Prime Factors

RE, plz help
code : C
#include<stdio.h>
#include<math.h>
long long int nn=60000;
long long int prime[70000]={0};
long long int list[60002],ary[60002]={0};
long long int listsize;

long long int primefact(long long n);
long long int seve(long long int n);
int main()
{
seve(nn);
long long int N,k,i;
scanf("%lld",&N);
while(N!=0)
{
if(N==2147483647)
printf("2147483647 = 2147483647\n");
else if(N == -2147483647)
printf("-2147483647 = -1 * 2147483647\n");
else if(N==1)
printf("1 = 1\n");
else if(N==-1)
printf("-1 = -1\n");
else
{
k=N;
if(N<0)
{
printf("%lld = -1",N);
N=N*(-1);

}
else
{
printf("%lld = ",N);
}

primefact(N);

if(k<0)
{
for(i=0; i<listsize; i++)
printf(" * %lld",list[i]);
}
else
{
printf("%lld",list[0]);
for(i=1; i<listsize; i++)
printf(" * %lld",list[i]);
}
printf("\n");
}
scanf("%lld",&N);
}
return 0;
}

long long int primefact(long long int n)
{
listsize=0;
long long int i;
for(i=0; prime[i]<=n; i++)
{
if(n%prime[i]==0)
{
while(n%prime[i]==0)
{
n=n/prime[i];
list[listsize]=prime[i];
listsize++;
}
}
}
return 0;
}
long long int seve(long long int N)
{
if(N<0) N=N*(-1);
long long int i,j,I;
I=(int)(sqrt((double)N));
for(i=3; i<=I; i=i+2)
{
if(ary[i]==0)
{
for(j=i*i; j<=N; j+=i+i)
{
ary[j]=1;
}
}
}
j=1;
prime[0]=2;
for(i=3; i<=N; i=i+2)
if(ary[i]==0)
{
prime[j]=i;
j++;
}
return 0;
}
shuvokr
New poster

Posts: 28
Joined: Tue Oct 02, 2012 8:16 pm

### Re: 583 - Prime Factors

print x not *
brianfry713
Guru

Posts: 1861
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 583 - Prime Factors

i am getting CE!!! i can't understand why??
Code: Select all
`#include <stdio.h>#include <math.h>int main(){    long N;    while(scanf("%ld", &N))    {        if(N == 0)            break;        printf("%ld = ", N);        if(N < 0)        {            printf("-1 x ");            N = -N;        }        long sq = sqrt(N);        int factor[10000], l = 0, i;        while(N % 2 == 0)        {            factor[l++] = 2;            N /= 2;        }        for(i = 3; i <= sq; i += 2)        {            while(N % i == 0)            {                factor[l++] = i;                N /= i;            }        }        if(N != 1)            factor[l++] = N;        for(i = 0; i < l; i++)        {            printf("%d ", factor[i]);            if(i != l-1)                printf("x ");        }        printf("\n");    }    return 0;}`
shuza
New poster

Posts: 4
Joined: Fri May 04, 2012 1:59 am

### Re: 583 - Prime Factors

That code is TLE. You can see the reason for a Compile Error by clicking "My Submissions".
brianfry713
Guru

Posts: 1861
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Previous