583 - Prime Factors

[unuguntsai]

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++ )
        {
            ...
        }

that is possibly your mistake

thank you angga888~
i got AC already~

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

[mohiul alam prince]

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

[unuguntsai]

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 ~
thanks your explain~

[marcadian]

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.


My program got TLE, please help me, I've tried it with many test case

[artem]

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

[valar2006]

Huh? xenical addiction
buying lorazepam no prescription buying omeprazole online
levitra canada cipro use

[marcadian]

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

[Fuad Hassan_IIUC(DC)]

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;
}

[vice]

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]

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]

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[])
{
String OneLine=readInt();
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("");
OneLine=readInt();
}
}

/* 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.
*/
public static String readInt()
{
int car;
boolean nochars = true, minus=false;
StringBuffer r=new StringBuffer(100);

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

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

while(true)
{

if (car<'0' || car>'9') break;
{
r.append((char)car);
nochars = false;
}
car = System.in.read();
}
}
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]

The code is accepted but how can i make it faster.Please help me.

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]

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]

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

[serur]

precalc primes