583 - Prime Factors

[soyoja]

I tried to solve problem 583, but I encounter "Time Limit Exceed" error.

I think that this problem need to make prime array, and using brute

force algorithm. But when I make prime array, it takes too long time.

Anyone suggest me some helps?

Plz your kindly advise. Thanks.

[Stefan Pochmann]

Maybe it helps if you submit it under the correct number, namely 583?

[soyoja]

Sorry. my mis-typing. Problem number is not 586, but 583.

I corrected it. Now, Can you help me ? : )

[shahriar_manzoor]

To get the prime factors of a number you only need to divide it with the primes which r less than or equal to its square root. For example to get the prime factors of 69, you only need to divide it with 2, 3, 5, 7 and then the number that remains is 23 which is greater than its square root and is always prime or 1. So you need to generate primes upto sqrt(Max input).

[soyoja]

Finally, I have received a "Accepted" answer.

Thank you ^^;

[naushad]

i have tried p583 to solve. but unfortunately it is giving time limit exceed i m confident with my answers. but it takes time. plz help if u can.
regards,
naushad:-)

[shahriar_manzoor]

try numbers with large prime factors and see what happens

[popel]

You should know that what to do if you want to find the prime factors of a number efficiently.Trial for primes less that sqrt(x) and think a while.

[naushad]

i had done that. i checked upto sqrt of that number. but it is giiving time limit exceed. thats why i m confused.

[popel]

For Simplicity,
Let, if Pi is a Prime and x is a Natural Number:
x = P1.P2.P3.... ... ... Pn

Suppose, Pn > sqrt(x)
Then ,
P1.P2.P3.... ... ... Pn-1 <sqrt(x)

So a Number x CANNOT have more than ONE prime factor greater than sqrt(x)

Can you smell something new ?

[naushad]

i had tried earlier to do what u have told me. thanx for that. but that code is giving time limit exceed.....
have a look...

/* @JUDGE_ID: ******* 583 C++ "Naushad's Programming" */

/* "@BEGIN_OF_SOURCE_CODE" */
#include <stdio.h>
#include <math.h>
const long max = 50000;
int prime[max], pr[max], q[max];//100000
//prime()
void main()
{
//generating prime; 1->prime,0->non prime
long i;
for(i=0;i<max;i++)
prime[i] = 1;
long j;
prime[0] = 0;
prime[1] = 0;
for(i=2;i<=ceil(sqrt(max));)
{
for(j=i+i;j<=max;j+=i)
prime[j] = 0;
i++;
for(;!(prime[i]);i++);
}
j = 0;
for(i=0;i<max;i++)
{
if(prime[i])
pr[j++] = i;
}

long x,y,z;
while(scanf("%ld",&z)!=EOF)
{
if(z==0)break;
for(i=0;i<max;i++)
q[i] = 0;

x = labs(z);
if(x==1)
{
printf("%ld = %ld\n",z,z);
continue;
}
y = x;
int counter = 0;
printf("%ld = ",z);
for(i=0;pr[i]<=sqrt(x);i++)
{
while((y%pr[i])==0)
{
counter++;
q[i]++;
y /= pr[i];
}
}
if(y!=1)
counter++;

if(z<0)
printf("-1 x ");

counter--;

for(i=0;pr[i]<=sqrt(x);i++)
{
while(q[i]--)
{
printf("%d ",pr[i]);
if(counter--)
printf("x ");
}
}

if(y!=1)
printf("%ld",y);

printf("\n");

}
}
/*"@END_OF_SOURCE_CODE" */

[popel]

Better you can compare with my code.
Here's my one:
[cpp]
#include<stdio.h>
#include<math.h>

int prime[5000];
int cp();

int cp(){
int a,t;
int b,c=3,p;
prime[0]=2;prime[1]=3;prime[2]=5;
for(a=7;a<=47000;a+=2){
p=0;
t=(int)sqrt((double)a);
for(b=2;(b<=t)&&(p!=1);b++)
{if(a%b==0)p=1;}

if(p!=1){prime[c]=a;c++;}
}
return(c);
}
void main(){
int m,c,j,last,hit,k,t,s;
c=cp();
while(scanf("%i",&k)==1){
if(k==0)break;
printf("%i =",k);
hit=0;
t=abs(k);
s=(int)sqrt((double)t);
if(k<0)printf(" -1 x");
for(m=0;m<=c-1;m++){
if(prime[m]>s)break;
do{
j=t%prime[m];
if(j==0){
t/=prime[m];
if(hit==0)
{printf(" %i",prime[m]);hit++;}
else printf(" x %i",prime[m]);
}
}while(j==0);
}
last=t;
if(last>1){
if(hit!=0)printf(" x %i",last);
else printf(" %i",last);}
printf("\n");
}

}
[/cpp]

[naushad]

unfortunately ur code gives sqrt: Domain error

[popel]

My solution should give you compile error. I don't know why but there
may be some error when I was editing it in the poll editor.
See,I have corrected it. (There was a declaration double a;it should be
int a)
Send it, And see,It will get accepted ,no Runtime Error.
And I cannot find any valid input for domain error.If the input is 2^31
or -2^31 it gives a wrong output but one can easily overcome it.
All judge inputs are [-2^31+1 , 2^31-1]

[Lekva]

[pascal]
var
code,c:integer;
j,i,n:longint;
s:string;

function prime(n:longint):boolean;
begin
prime:=true;
for j:=2 to trunc(sqrt(n)) do
if n mod j=0 then
begin
prime:=false;
exit;
end;
if c=1 then
write(' x ');
write(n);
end;

procedure rec(n:longint);
begin
inc(i);
while n mod i=0 do
begin
n:=n div i;
if c=0 then
begin
write(i);
c:=1;
end
else
write(' x ',i);
end;
if prime(n) then
n:=1;
if n<>1 then
rec(n);
end;

begin
readln(s);
while s<>'0' do
begin
c:=0;
write(s,' = ');
if s='-2147483648' then
begin
s:='2147483648';
c:=1;
write(' x ',-1);
end;
if s='2147483648' then
begin
s:='1073741824';
if c=0 then
write(2)
else
write(' x ',2);
c:=1;
end;
val(s,n,code);
if n<0 then
begin
n:=abs(n);
write(-1);
c:=1;
end;
i:=1;
if n<>1 then
rec(n)
else
if s<>'-1' then
write(1);
writeln;
readln(s);
end;
end.[/pascal]