## 583 - Prime Factors

Moderator: Board moderators

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 ??
unuguntsai
New poster

Posts: 6
Joined: Mon Aug 15, 2005 4:40 am

Hi
you have generated prime up to 46337 and your prime counter value
Cprime is 4791
when the input is 2147483647 and prime[i] = 46337 and i = 4791
at that time your this condition prime[i] * prime[i] <= 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

mohiul alam prince
Experienced poster

Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

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[i] = 46337 and i = 4791
at that time your this condition prime[i] * prime[i] <= 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 ~
unuguntsai
New poster

Posts: 6
Joined: Mon Aug 15, 2005 4:40 am

### 583 Prime Factor TLE

Code: Select all
`program faktorprime583;var     n,i,l,s:longint;begin        readln(n);        while n<>0 do begin                       write(n,' = ');                 if (n<0) and (n<>-1) then                        write(-1,' x ');                 if n=-1 then                 begin                        writeln(n);                        readln(n);                        continue;                 end;                 n:=abs(n);                 if n=1 then                 begin                        writeln(n);                        readln(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;                 readln(n);        end;end.`

New poster

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

Try first to generate all primes < sqrt(2^31) and then instead "n mod i" use "n mod prime[i]", where prime[i] the next prime number
artem
New poster

Posts: 17
Joined: Thu Jun 09, 2005 5:01 pm

valar2006
New poster

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

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        readln(n);        while n<>0 do begin                       write(n,' = ');                 if (n<0) and (n<>-1) then                        write(-1,' x ');                 if n=-1 then                 begin                        writeln(n);                        readln(n);                        continue;                 end;                 n:=abs(n);                 if n=1 then                 begin                        writeln(n);                        readln(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;                 readln(n);        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: 45
Joined: Sun Jun 26, 2005 6:21 am

### 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[i]<<' ';
if(i<k+1)
cout<<'X'<<' ';
}
cout<<endl;

}
}
}
return 0;
}
New poster

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

### 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;}`
vice
New poster

Posts: 3
Joined: Thu May 12, 2005 6:09 pm

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

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

### 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);
}
}
MAK
New poster

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

### 583 how can i make it faster

Code: Select all
`#include<stdio.h>#include<math.h>#define MAX 5000#define P 46401long 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]
sohag144
New poster

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

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

Posts: 1
Joined: Mon Mar 27, 2006 4:16 pm
Location: Lahore, Pakistan

thank you very much for your attention.
Is there anybody to give me more suggestion or code?
sohag144
New poster

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

precalc primes
serur
A great helper

Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

PreviousNext