583 - Prime Factors

Moderator: Board moderators

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

583 Prime Factors! Help.

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?

Last edited by soyoja on Mon Jun 03, 2002 5:08 pm, edited 1 time in total.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Maybe it helps if you submit it under the correct number, namely 583?

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

Yes. It's my mistake -_-, Not 586, but 583.

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

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

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am
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
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

Thank you

Thank you ^^;

New poster
Posts: 9
Joined: Sat Jul 13, 2002 1:07 pm
Contact:

583

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,

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

try

try numbers with large prime factors and see what happens

popel
New poster
Posts: 33
Joined: Fri Mar 15, 2002 2:00 am
Contact:
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.

New poster
Posts: 9
Joined: Sat Jul 13, 2002 1:07 pm
Contact:
i had done that. i checked upto sqrt of that number. but it is giiving time limit exceed. thats why i m confused.

popel
New poster
Posts: 33
Joined: Fri Mar 15, 2002 2:00 am
Contact:
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 ?

New poster
Posts: 9
Joined: Sat Jul 13, 2002 1:07 pm
Contact:
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 = 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++);
}
j = 0;
for(i=0;i<max;i++)
{
if(prime)
pr[j++] = i;
}

long x,y,z;
while(scanf("%ld",&z)!=EOF)
{
if(z==0)break;
for(i=0;i<max;i++)
q = 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<=sqrt(x);i++)
{
while((y%pr)==0)
{
counter++;
q++;
y /= pr;
}
}
if(y!=1)
counter++;

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

counter--;

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

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

printf("\n");

}
}
/*"@END_OF_SOURCE_CODE" */

popel
New poster
Posts: 33
Joined: Fri Mar 15, 2002 2:00 am
Contact:
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]
Last edited by popel on Thu Aug 01, 2002 3:42 pm, edited 1 time in total.

New poster
Posts: 9
Joined: Sat Jul 13, 2002 1:07 pm
Contact:
unfortunately ur code gives sqrt: Domain error

popel
New poster
Posts: 33
Joined: Fri Mar 15, 2002 2:00 am
Contact:

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
New poster
Posts: 1
Joined: Fri Jan 03, 2003 9:50 pm

583

[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
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;