583 - Prime Factors

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

Moderator: Board moderators

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

583 Prime Factors! Help.

Post by soyoja » Sun Jun 02, 2002 8:59 pm

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

Post by Stefan Pochmann » Sun Jun 02, 2002 11:41 pm

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.

Post by soyoja » Mon Jun 03, 2002 5:09 pm

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

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

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Post by shahriar_manzoor » Mon Jun 03, 2002 6:02 pm

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

Post by soyoja » Wed Jun 05, 2002 9:00 pm

Finally, I have received a "Accepted" answer.

Thank you ^^;

naushad
New poster
Posts: 9
Joined: Sat Jul 13, 2002 1:07 pm
Location: Dhaka, Bangladesh
Contact:

583

Post by naushad » Wed Jul 24, 2002 8:51 pm

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

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

try

Post by shahriar_manzoor » Thu Jul 25, 2002 1:17 am

try numbers with large prime factors and see what happens

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

Post by popel » Fri Jul 26, 2002 1:37 pm

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
New poster
Posts: 9
Joined: Sat Jul 13, 2002 1:07 pm
Location: Dhaka, Bangladesh
Contact:

Post by naushad » Fri Jul 26, 2002 4:44 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by popel » Sat Jul 27, 2002 12:32 pm

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 ? 8)

naushad
New poster
Posts: 9
Joined: Sat Jul 13, 2002 1:07 pm
Location: Dhaka, Bangladesh
Contact:

Post by naushad » Wed Jul 31, 2002 8:00 am

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
Location: Dhaka, Bangladesh
Contact:

Post by popel » Wed Jul 31, 2002 4:37 pm

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.

naushad
New poster
Posts: 9
Joined: Sat Jul 13, 2002 1:07 pm
Location: Dhaka, Bangladesh
Contact:

Post by naushad » Thu Aug 01, 2002 1:44 pm

unfortunately ur code gives sqrt: Domain error :oops:

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

Post by popel » Thu Aug 01, 2002 3:51 pm

:-? :-? :-? :-? :-? :-? :-? :-? :-? :-? :-? :-? :-? :-? :-?
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

Post by Lekva » Fri Jan 03, 2003 9:54 pm

:cry: [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]
Hi.

Post Reply

Return to “Volume 5 (500-599)”