## 583 - Prime Factors

Moderator: Board moderators

unuguntsai
New poster
Posts: 6
Joined: Mon Aug 15, 2005 4:40 am
angga888 wrote:I think you should change this:

Code: Select all

``````for( i = 0 ; prime[i]*prime[i] <= x ; i++ )
{
...
} ``````
into:

Code: Select all

``````for( i = 0 ; i < Cprime && prime[i]*prime[i] <= x ; i++ )
{
...
} ``````
thank you angga888~

but why i need to put " i < Cprime " in my code ??
will i over Cprime ??

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
Hi
you have generated prime up to 46337 and your prime counter value
Cprime is 4791
when the input is 2147483647 and prime = 46337 and i = 4791
at that time your this condition prime * prime <= x will satisfied
but when you increase i at that time prime[4792] will contain a garbage value because you have generated 4791 prime's

suppose the garbage value prime[4792] = 1 and the input
is 2147483647

then this is fall into a infinite loop and it always print 1.
That's why you have got OLE.

Thanks
MAP

unuguntsai
New poster
Posts: 6
Joined: Mon Aug 15, 2005 4:40 am
mohiul alam prince wrote:Hi
you have generated prime up to 46337 and your prime counter value
Cprime is 4791
when the input is 2147483647 and prime = 46337 and i = 4791
at that time your this condition prime * prime <= x will satisfied
but when you increase i at that time prime[4792] will contain a garbage value because you have generated 4791 prime's

suppose the garbage value prime[4792] = 1 and the input
is 2147483647

then this is fall into a infinite loop and it always print 1.
That's why you have got OLE.

Thanks
MAP

Ahh....I see ~

New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:

### 583 Prime Factor TLE

Code: Select all

``````program faktorprime583;
var     n,i,l,s:longint;
begin
while n<>0 do begin
write(n,' = ');
if (n<0) and (n<>-1) then
write(-1,' x ');
if n=-1 then
begin
writeln(n);
continue;
end;
n:=abs(n);
if n=1 then
begin
writeln(n);
continue;
end;
l:=round(sqrt(n))+1;
repeat
if n mod 2=0 then
begin
write(2);
n:=n div 2;
if n<>1 then write(' x ');
end;
until (n mod 2<>0);
i:=3;
repeat
if ((n mod i)=0) then
begin
write(i);
n:=n div i;
if n<>1 then write(' x ');
end
else
inc(i,2);
until
(i>=l) or (n=1);
if n>1 then write(n);
writeln;
end;
end.
``````

artem
New poster
Posts: 17
Joined: Thu Jun 09, 2005 5:01 pm
Try first to generate all primes < sqrt(2^31) and then instead "n mod i" use "n mod prime", where prime the next prime number

valar2006
New poster
Posts: 2
Joined: Sat Jul 23, 2005 9:47 pm

New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:
thx but instead of generate all prime, I think it's better to use relative prime (shortest code, less memory and not TLE) so my final code like this

Code: Select all

``````program faktorprime583;
var     n,i,l,s:longint;
begin
while n<>0 do begin
write(n,' = ');
if (n<0) and (n<>-1) then
write(-1,' x ');
if n=-1 then
begin
writeln(n);
continue;
end;
n:=abs(n);
if n=1 then
begin
writeln(n);
continue;
end;
l:=round(sqrt(n))+1;
repeat
if n mod 2=0 then
begin
write(2);
n:=n shr 1;
if n<>1 then write(' x ');
end;
until (n mod 2<>0);
if n>1 then
repeat
if n mod 3=0 then
begin
write(3);
n:=n div 3;
if n<>1 then write(' x ');
end;
until (n mod 3<>0);

if n>1 then
i:=6;
begin
repeat
while ((n mod (i-1))=0) do
begin
write(i-1);
n:=n div (i-1);
if n<>1 then write(' x ');
end;
while ((n mod (i+1))=0) do
begin

write(i+1);
n:=n div (i+1);
if n<>1 then write(' x ');
end;
inc(i,6);
until
((i-1)>l) or (n=1);

if n>1 then write(n);
end;
writeln;
end;
end.
``````
when I submit, the real time status says that CPU=9.164
what does it means??is it run time program in seconds??

New poster
Posts: 18
Joined: Fri Jan 07, 2005 9:35 pm

### 583 Run time error??????????

plz help me out
#include<stdio.h>
#include<iostream.h>
#include<math.h>
#define max 48009
long long seive[max];
long long prmcol[max];
void genseive()
{
long long m,n;
long long sq=sqrt(max);
seive[0]=seive[1]=1;
for(m=2;m<=sq;m++)
{
for(n=m+m;n<max;n+=m)
seive[n]=1;
}
n=-1;
for(m=2;m<max;m++)
{
if(seive[m]==0)
prmcol[++n]=m;

}
}

int main()
{
long long i,result,j,k,input,m,flag;
static long long fact[max];
genseive();
while(cin>>input)
{
if(input==0)
break;
else if(input==1||input==-1)
cout<<input<<' '<<"="<<' '<<input<<endl;
else{
flag=0;
for(m=0;m<max;m++)
fact[m]=0;
j=0;result=abs(input);k=0;
if(seive[abs(input)]==0)
{
if(input<0)
{
cout<<input<<' '<<"="<<' '<<"-1"<<' '<<'X'<<' ';
cout<<abs(input)<<endl;
flag++;
}
else
{
cout<<input<<' '<<"="<<' '<<input<<endl;
flag++;
}
}
if(flag==0)
{
for(i=prmcol[j];prmcol[j]<=sqrt(abs(input));)
{
if((result%i)==0)
{
fact[k]=i;
result=result/i;
i=prmcol[j];
if(seive[result]==0)
{
fact[k+1]=result;
break;
}
k++;
}
else i=prmcol[++j];
}

if(input<0)
cout<<input<<' '<<"="<<' '<<"-1"<<' '<<'X'<<' ';
else cout<<input<<' '<<"="<<' ';
for(i=0;i<=k+1;i++)
{

cout<<fact<<' ';
if(i<k+1)
cout<<'X'<<' ';
}
cout<<endl;

}
}
}
return 0;
}

vice
New poster
Posts: 3
Joined: Thu May 12, 2005 6:09 pm
Contact:

### 583 tle problem

I always got tle when i submit my code, anyone know better algorithm to solve this problem?

Code: Select all

``````#include <stdio.h>
#include <math.h>
int isPrime(int num)
{
int j;
for (j = 2 ;j<num ;j++ )
{
if (num%j == 0)
return 0;
if (j>sqrt(num))
{
return 1;
}
}
return 0;
}

void primeFact(int x)
{
int result [100];
int i;
int j = 0;
int temp = x;

printf("a");
if (x<0)
{
result[j++] = -1;
x *= -1;
}

for (int i = 2 ;i<=x ;i++ )
{
if (x%i == 0 && isPrime(i))
{
while (x%i == 0)
{
result[j++] = i;
x /= i;

}
}
}
result[j] = '\0';

printf("%d = %d",temp, result[0]);

for (i = 1; result[i]!='\0'; i++)
{
printf(" x %d", result[i]);
}
printf("\n");
}

int main(int argc, char *argv[])
{
int x;

while (scanf("%d", &x)!= 0)
{
if (x==0)
break;

primeFact(x);

}
return 0;
}
``````

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### Better algo ...

Hi, I 've solved the problem with precalculating prime numbers withing the range of the square root of the highest number(2^31 - 1) which is around 46342 ..... If i have primes upto 46342 then i can check any number withing the range whether it is divisible( if so, then how many times by which prime factor ) or prime.

code for generating primes :
~~~~~~~~~~~~~~~~~~~

Code: Select all

``````        cprime = 0;
prime[cprime ++] = 2;

/*
GENERATING PRIMES UPTO 46342
*/
for (k=3; k<=46342; k+=2)
{
for (i=0; prime[i]*prime[i] < k; i++)
{
if (k % prime[i] == 0)
break;
}

if (prime[i]*prime[i] > k)
{
prime[cprime++] = k;
}
}
/*
long long prime[4800]; this array is for precalculated primes,
BE SURE, there are less than 4800 in the
range :)
long long i, k, cprime;   these are indices
*/
``````

Now, check with these precalculated primes ... HOPE, this helps ...

MAK
New poster
Posts: 28
Joined: Sun Oct 23, 2005 3:44 pm

### 583 TLE JAVA

I've tried every other method I know (sieve etc.) and I'm quite sure this one's the fastest, but still keep getting TLE. Is it because it's been coded in JAVA? Can anyone help?

class Main
{

public static final boolean DEBUG=false;

public static void main(String args[])
{
boolean First;
long value;
int count;

while (OneLine!=null)
{
First=true;

value=Long.parseLong(OneLine);
if (value==0) break;

System.out.print(OneLine);
System.out.print(" = ");

if (value<0)
{
First=false;
System.out.print("-1");
value=-value;
}

while ((value&1)==0)
{
if (!First)
{
System.out.print(" x ");
}
else
First=false;

System.out.print('2');

value=value>>1;
}

int tmp=(int)Math.sqrt(value)+1;

for (count=3;count<=tmp;count+=2)
{
while (value%count==0)
{
if (!First)
{
System.out.print(" x ");
}
else
First=false;

System.out.print(count);

value=value/count;
}
}

if (value>1)
{
if (!First)
{
System.out.print(" x ");
}
System.out.print(value);

}
System.out.println("");
}
}

/* Returns a string from stdin containing an int.
* Use Integer.parseInt on this to get the actual value.
* Returns null if there are no integers coming in from stdin.
*/
{
int car;
boolean nochars = true, minus=false;
StringBuffer r=new StringBuffer(100);

try
{
do{
if (car<0) return null;
} while ((car>'9' || car<'0') && car!='-');

if (car=='-')
{
r.append((char)car);
}
else if ( nochars && car<0) return null;

while(true)
{

if (car<'0' || car>'9') break;
{
r.append((char)car);
nochars = false;
}
}
}
catch (Exception e)
{
return null;
}

if (nochars && car<0)
{
return null;
}
else if (r.length()==0 && r.charAt(0)=='-')
return null;

return r.toString();

}

public static final void dout(int c)
{
if (DEBUG)
System.out.println(c);
}
public static final void dout(String c)
{
if (DEBUG)
System.out.println(c);
}
}

sohag144
New poster
Posts: 14
Joined: Mon Feb 27, 2006 4:12 pm
Contact:

### 583 how can i make it faster

Code: Select all

``````#include<stdio.h>
#include<math.h>

#define MAX 5000
#define P 46401

long factor[MAX];
long prime[P];
long p[MAX];

void main()
{
long n,count,i;
long j;

/*freopen("in.txt","r",stdin);*/
prime[0]=prime[1]=1;

for(i=2; i<=(long)sqrt(P-1); i++)
{
if(prime[i]==0)
{
for(j=i*i; j<=P-1; j=j+i)
{
prime[j]=1;
}
}
}
j=0;
for(i=0; i<=P-1; i++)
{
if(prime[i]==0) p[j++]=i;
}

while(scanf("%ld",&n)!=EOF)
{
if(n==0) break;

printf("%ld = ",n);

if(n<0)
{
printf("-1 x ");
n=-n;
}

count=0;
for(i=0; p[i]<=(long)sqrt(n); i++)
{
while(n%p[i]==0)
{
n=n/p[i];
factor[count]=p[i];
count++;
}
}
if(n!=1) factor[count++]=n;

for(i=0; i<count; i++)
{
printf("%ld",factor[i]);
if(i!=count-1)printf(" x ");
}
printf("\n");
}
}
``````
[quote][/quote]

raheels
New poster
Posts: 1
Joined: Mon Mar 27, 2006 4:16 pm
Location: Lahore, Pakistan
Contact:
I have collected some thoughts on issues of prime numbers. I guess a visit to my blog (http://spaces.msn.com/raheelshahzad/) would be very helpful to you.

sohag144
New poster
Posts: 14
Joined: Mon Feb 27, 2006 4:12 pm