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

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 ~
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", where prime 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<<' ';
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