## 583 - Prime Factors

Moderator: Board moderators

### 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.
soyoja
Experienced poster

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

Maybe it helps if you submit it under the correct number, namely 583?
Stefan Pochmann
A great helper

Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany

### 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 ? : )
soyoja
Experienced poster

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

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).
shahriar_manzoor

Posts: 400
Joined: Sat Jan 12, 2002 2:00 am

### Thank you

Thank you ^^;
soyoja
Experienced poster

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

### 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,
New poster

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

### try

try numbers with large prime factors and see what happens
shahriar_manzoor

Posts: 400
Joined: Sat Jan 12, 2002 2:00 am

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.
popel
New poster

Posts: 33
Joined: Fri Mar 15, 2002 2:00 am

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

Posts: 9
Joined: Sat Jul 13, 2002 1:07 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 ?
popel
New poster

Posts: 33
Joined: Fri Mar 15, 2002 2: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[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" */
New poster

Posts: 9
Joined: Sat Jul 13, 2002 1:07 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.
popel
New poster

Posts: 33
Joined: Fri Mar 15, 2002 2:00 am

unfortunately ur code gives sqrt: Domain error
New poster

Posts: 9
Joined: Sat Jul 13, 2002 1:07 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]
popel
New poster

Posts: 33
Joined: Fri Mar 15, 2002 2:00 am

### 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;
end;
end.[/pascal]
Hi.
Lekva
New poster

Posts: 1
Joined: Fri Jan 03, 2003 9:50 pm

Next