## 583 - Prime Factors

Moderator: Board moderators

My outputs are all right :-?
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius
Morning
Experienced poster

Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Hi !! Morning this WA was hard to find I'm sure that is a stupid thing this is the I/O that I use
input :
Code: Select all
`46337926740`

Code: Select all
`46337 = 46337 x 192674 = 2 x 46337 x 1`

My ouput
Code: Select all
`46337 = 4633792674 = 2 x 46337`

Hope it helps
Keep posting !!

Ghust_omega
Experienced poster

Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

it helps a lot,i've gotten AC
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius
Morning
Experienced poster

Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

### 583~~with WA~~~><"

Well~~I don't know where is wrong~~
Can anyone help me????
Code: Select all
`#include <stdio.h>#include <stdlib.h>#include <math.h>int main(void){  int n,i,t,m,a[4800],k;  k=0;  for(i=2;i<=46342;i++)  {    t=0;    n=2;    while(n<=sqrt(i)&&t==0)    {        if(i%n==0)            t=1;        else            n++;    }    if(t==0)    {        k++;        a[k]=i;    }  }  scanf("%d",&n);  while(n!=0)  {    t=0;    printf("%d = ",n);    if(n==1)        printf("%d",n);    if(n<0)    {        printf("-1");        t=1;        n=-n;    }    i=1;    m=n;    while(n!=1&&a[i]<=sqrt(m)&&i<=4792)    {        if(n%a[i]==0)        {            n=n/a[i];            if(t!=0)                printf(" * %d",a[i]);            else                printf("%d",a[i]);            t++;        }        else            i++;    }    if(n!=1)    {      if(t==0)        printf("%d",n);      else        printf(" * %d",n);    }    printf("\n");    scanf("%d",&n);  }  system("PAUSE");  return 0;}`
Wei
New poster

Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm

Hi
i have just changed x instead of *
and
i don't use // system("PAUSE");
that's why u have got AC

MAP

mohiul alam prince
Experienced poster

Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Well~~Thx a lot ~~~
I got AC then ~~~
Wei
New poster

Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm

### 583 (prime factor prob) TLE

hey I use this simple and clear algorithm but get TLE (Can I use array with prime numbers to get AC?) I don't want this solution.Is there another way other that.
Excuse me it is not correct I send the correct one in third post
#include <iostream>

using namespace std;

int main()
{

int num;
int number;
int count,i;
bool prime=true;

while (cin>>num)
{
number=num;
count = 1;
prime=true;

if(num<0)
{
number=number*(-1);

}
else
count=0;

while(number%2==0)
{
count++;
number/=2;
}

for(i=3;i*i<=number;i+=2)// bug is here
{
prime=true;
while(number%i==0)
{
count++;
number/=i;
prime=false;
}

}

if(prime==true)
{
count++;
}

cout <<num <<" = ";

for(i=0;i<count-1;i++)
{
}

}
}
Last edited by narsys on Sun Jun 19, 2005 4:59 am, edited 1 time in total.
narsys
New poster

Posts: 5
Joined: Sat Jun 04, 2005 6:34 am

Check the problem input/output, your problem should at least be right for those samples and then try to send it, for input:

-190

problem output:
-190 = -1 x 2 x 5 x 19

-190 = -1 x 2 x 5

besides, as I see you process input until the eof is reached and it must be until you read a 0, hope this helps,

Yandry.
neno_uci
Experienced poster

Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

### excuse me

I had changed my code before sent it and it was uncorrect
here is a correct code
#include <iostream>

using namespace std;

int main()
{

int num;
int number;
int count,i;
bool prime=true;

while (cin>>num && num!=0)
{
number=num;
count = 1;
// prime=true;

if(num<0)
{
number=number*(-1);

}
else
count=0;

while(number%2==0)
{
count++;
number/=2;
}

for(i=3;/*i*i*/ i<=number;i+=2)
{
// prime=true;
while(number%i==0)
{
count++;
number/=i;
// prime=false;
}

}

/* if(prime==true)
{
count++;
}*/

cout <<num <<" = ";

for(i=0;i<count-1;i++)
{
}

}
}
narsys
New poster

Posts: 5
Joined: Sat Jun 04, 2005 6:34 am

### 583~~TLE!!!~~

Why am i getting TLE????
plz help me.
#include<stdio.h>
#include<iostream.h>
#include<math.h>
#define max 480000
long long seive[max];
long long prmcol[max];
void genseive()
{
long long m,n;
long long sq=sqrt(max);
seive[0]=seive[1]=1;
for(m=2;m<=sq;m++)
{
for(n=m+m;n<max;n+=m)
seive[n]=1;
}
n=-1;
for(m=2;m<max;m++)
{
if(seive[m]==0)
prmcol[++n]=m;

}
}

int isprime(int a)
{
long long m;
for(m=0;m<max;m++)
{
if(a==prmcol[m])
return 1;
}
return 0;
}
int main()
{
long long i,result,j,k,input,m,flag;
static long long fact[max];
genseive();
while(cin>>input)
{
if(input==0)
break;
else if(input==1||input==-1)
cout<<input<<' '<<"="<<' '<<input<<endl;
flag=0;
for(m=0;m<max;m++)
fact[m]=0;
j=0;result=abs(input);k=0;
if(isprime(abs(input)))
{
if(input<0)
{
cout<<input<<' '<<"="<<' '<<"-1"<<' '<<'X'<<' ';
cout<<abs(input)<<endl;
flag++;
}
else
{
cout<<input<<' '<<"="<<' '<<input<<endl;
flag++;
}
}
if(flag==0)
{
for(i=prmcol[j];prmcol[j]<=sqrt(abs(input));)
{
if((result%i)==0)
{
fact[k]=i;
result=result/i;
i=prmcol[j];
if(isprime(result))
{
fact[k+1]=result;
break;
}
k++;
}
else i=prmcol[++j];
}

if(input<0)
cout<<input<<' '<<"="<<' '<<"-1"<<' '<<'X'<<' ';
else cout<<input<<' '<<"="<<' ';
for(i=0;i<=k+1;i++)
{

cout<<fact[i]<<' ';
if(i<k+1)
cout<<'X'<<' ';
}
cout<<endl;

}
}
return 0;
}
New poster

Posts: 18
Joined: Fri Jan 07, 2005 9:35 pm

I got this problem ACed without using the Sieve of E..., a good algorithm and small knowledge about prime numbers will do..., best wishes,

Yandry.
neno_uci
Experienced poster

Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

### 583 Why Output Limit Exceeded ??

I don't know why OLE ??

Code: Select all
`#include <iostream.h>#include <stdlib.h>int main(){      long long int n , x ;      long long int prime[4792] ;      int i , Cprime , k , ans ;      for( k=3 , Cprime=1 , prime[0]=2 ; k<46341 ; k+=2 )      {          for( i=0 ; prime[i]*prime[i] < k ;i++ )                if(k%prime[i]==0)             break;                    if(prime[i]*prime[i]>k)          prime[Cprime++]=k;      }      while( cin >> n && !cin.eof() && n != 0 )      {        cout << n << " = " ;        ans = 0 ;        if( n < 0 )        {          cout << "-1" ;          x = 0 - n ;          ans = 1 ;        }        else          x = n ;        for( i = 0 ; prime[i]*prime[i] <= x ; i++ )        {          while( x % prime[i] == 0 )          {            x /= prime[i] ;            if( ans )              cout << " x " << prime[i] ;            else            {              cout << prime[i] ;              ans = 1 ;            }          }        }        if( x != 1 )        {          if( ans )  cout << " x " ;          cout << x ;        }        else if( ans == 0 )  cout << "1" ;        cout << endl ;      }      return 0;}`
unuguntsai
New poster

Posts: 6
Joined: Mon Aug 15, 2005 4:40 am

Hi unuguntsai

I think for this input you are getting OLE
INPUT
2147483647

Thanks
MAP

mohiul alam prince
Experienced poster

Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

My Output

2147483647 = 2147483647

is it OLE ??
unuguntsai
New poster

Posts: 6
Joined: Mon Aug 15, 2005 4:40 am

I think you should change this:
Code: Select all
`for( i = 0 ; prime[i]*prime[i] <= x ; i++ )         {             ...        } `

into:

Code: Select all
`for( i = 0 ; i < Cprime && prime[i]*prime[i] <= x ; i++ )         {             ...        } `

angga888
Experienced poster

Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

PreviousNext