## 583 - Prime Factors

Moderator: Board moderators

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China
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

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
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

``````46337
92674
0
``````

Code: Select all

``````46337 = 46337 x 1
92674 = 2 x 46337 x 1

``````
My ouput

Code: Select all

``````46337 = 46337
92674 = 2 x 46337
``````
Hope it helps
Keep posting !!

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China
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

Wei
New poster
Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm
Contact:

### 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;
}
``````

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
Hi
i have just changed x instead of *
and
i don't use // system("PAUSE");
that's why u have got AC

MAP

Wei
New poster
Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm
Contact:
Well~~Thx a lot ~~~
I got AC then ~~~

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

### 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.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
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.

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

### 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++)
{
}

}
}

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

### 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<<' ';
if(i<k+1)
cout<<'X'<<' ';
}
cout<<endl;

}
}
return 0;
}

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
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.

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

### 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;
}``````

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
Hi unuguntsai

I think for this input you are getting OLE
INPUT
2147483647

Thanks
MAP

unuguntsai
New poster
Posts: 6
Joined: Mon Aug 15, 2005 4:40 am
My Output

2147483647 = 2147483647

is it OLE ??

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
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++ )
{
...
} ``````