583 - Prime Factors
Moderator: Board moderators
-
- 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?
Plz your kindly advise. Thanks.
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.
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
-
- 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 ? : )
I corrected it. Now, Can you help me ? : )
-
- System administrator & Problemsetter
- 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).
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,
naushad:-)

regards,
naushad:-)
-
- System administrator & Problemsetter
- Posts: 399
- Joined: Sat Jan 12, 2002 2:00 am
try
try numbers with large prime factors and see what happens
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" */
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" */
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]
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.















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]
583

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.