583 - Prime Factors

[off_algos]

well donot worry too much about a PE
the problem will be counted as solved only
yet,
the problem with ur progrm is that it outputs an extra space

if(a>1){printf("x ");}

when u print the last number u put an extra space
and thats all the mistake that u have done and nothing more

[Jalal]

Less the limit of ur prima and hasil variable.

these are too much to show that error

[Jalal]

Use a faster sieve method for finding primes.
and then do the other things.
hope can help.

[ezra]

please help me. why did i get wa for this problem ?
here is my code.
[c]#include<stdio.h>
#include<math.h>

void generate(char flag[],long prima[])
{
long i,j,k;
for(i=0;i<50000;i++)
{
flag[i]='n';
prima[i]=0;
}
prima[0]=2;
j=1;
for(i=3;i<50000;i+=2)
if(flag[i]=='n')
{
prima[j]=i;
j++;
for(k=2;(i*k)<50000;k++)
flag[i*k]='y';
}
}

void main()
{
long i;
char flag[50000];
long p;
long prima[50000];
generate(flag,prima);
while(scanf("%ld",&p)&&p)
{
printf("%ld = ",p);
if(p==1)
{
printf("1\n");
continue;
}
if(p<0)
{
printf("-1");
p=p*(-1);
for(i=0;p%prima[i]!=0&&(double)prima[i]<=sqrt((double)p);i++);
}
else
{
for(i=0;p%prima[i]!=0&&(double)prima[i]<=sqrt((double)p);i++);
if(p%prima[i]==0)
{ printf("%ld",prima[i]);
p/=prima[i];
}
if((double)prima[i]>sqrt((double)p))
{
printf("%ld\n",p);
continue;
}
}

while((double)prima[i]<=sqrt((double)p)&&p!=1)
{
for(;(double)prima[i]<=sqrt((double)p)&&p%prima[i]!=0;i++);
if(p%prima[i]==0)
{ printf(" x %ld",prima[i]);
p/=prima[i];
}
}
if(p!=1)
printf(" x %ld",p);
printf("\n");
}
}
[/c]

[Hisoka]

hello Ezra.....

I think your program can failed when input is like this:

Code: Select all

49
64

your output will be like this

Code: Select all

77
88

because of this:

Code: Select all

else
      {
         for(i=0;p%prima[i]!=0&&(double)prima[i]<=sqrt((double)p);i++);
         if(p%prima[i]==0)
         {   printf("%ld",prima[i]);
            p/=prima[i];
         }
         if((double)prima[i]>sqrt((double)p))
         {
            printf("%ld\n",p);
            continue;
         }
      }

I'm sorry if I wrong, because I cannot compile your program in my computer, because it should gave me troubleshotting. except this I cannot find any mistake in your program. And once again, I think if you use sqrt in your loop, like this:

Code: Select all

for(i=0;p%prima[i]!=0&&(double)prima[i]<=sqrt((double)p);i++);


will be increase your time limit.

bye......

[ezra]

wow, hisoka
you're so clever. you can find where the incorrect part of my algo/code.
thanks a lot for your help and suggestion.

[lendlice]

anyone can help me
[cpp]//583
#include<stdio.h>
#include<math.h>
long primestack[5000];
int num=0;
long prime(long n)
{
int i,j,tr=0;
num=0;
for(i=2;i<=n;i++)
{
for(j=2,tr=0;j<=sqrt(i);j++)
{
if(i%j==0)
{
tr=1;
break;
}
if(j>=3)
j++;
}
if(tr==0&&i!=0&&i!=1)
{
primestack[num]=i;
num++;
}
}
return(num);
}
main()
{
long n,tr=0;
int i=0;
while(scanf("%ld",&n)==1)
{
if(n==0)
break;
printf("%ld =",n);
if(n==1)
printf(" 1");
if(n<0)
{
printf(" -1");
n=n*-1;
tr=1;
}
prime(n);
while(n!=1)
{
for(i=0;i<num;i++)
{
if(n%primestack[i]==0)
{
n=n/primestack[i];
if(tr==0)
{
printf(" %ld",primestack[i]);
tr=1;
}
else
printf(" x %ld",primestack[i]);
break;
}
}
}
printf("\n");
tr=0;
}
}
[/cpp]

[Joseph Kurniawan]

You don't have to store the prime factors in array.
Here's some trick of mine for this problem :

in your long prime ():
1. as long as the input number is even you divide it by two and after
the division you print the number '2'.
while(input%2==0){ input/=2; printf("2");}
2. If after step one the input is still larger than one, the remaining number
now must be an odd number. Since this rule apply :
odd * odd = odd
odd * even = even
even * odd = even
even * even = even
We can see that odd numbers are only divisible by odd numbers too.
So the next step :
for(divisor=3;input>1; divisor+=2){
while(input%divisor==0){input/=divisor;printf("%i",divisor);}
}

Hope it helps !!

[lendlice]

I used to this way to write this program.
but i got time limit.
My friend told if you use this way to write this program
you will spent a lot of time to do some useless thing.
for example:
if a number n mod 3 is not zero,so the number mod 6 is not
zero,too.
so,my friend told me use a array to save prime.

[Joseph Kurniawan]

That's why I used "divisor+=2" to ensure the divisor is odd number.
Besides using "divisor+=2", the divisor value increases quite quickly, so
it should save more time.
Maybe the second step should be:

square = sqrt ( input ) ;
if ( square % 2 == 0 ) square ++ ;
for ( divisor = 3 ; input > 1 && divisor <= square ; divisor += 2 )
while ( input % divisor == 0 ) {
printf ( "%i" , divisor ) ;
input /= divisor ;
}
}
if ( input > 1 ) printf ( "%i" , input ) ;

I got AC in 4,..... sec ( under 5 for sure ) using this method.

[lendlice]

thanks
I got AC.
but i still use store prime.
and i got AC in 2 sec

[SilVer DirectXer]

[cpp]
#include <iostream>
#include <stdlib.h>
#include <math.h>
using namespace std;
int n,i,j,k,l;
int num[50];
int factor;
bool neg;
int to;
void main(void)
{
while (1)
{
neg=false;
cin>>n;
j=n;
if (n==1)
{
cout<<"1 = 1"<<endl;
continue;
}


if (n==0)
exit(0);
if (n<0)
{
neg=true;
n*=-1;
}

k=(int)sqrt((int)j);
factor=2;
l=n;
to=-1;
while(1)
{
if (factor>k+1)
{
to++;
num[to]=l;
l=1;
}
if (l==1)
break;
if (l % factor==0)
{
to++;
num[to]=factor;
l/=factor;
}
else
{
factor++;
}
}
cout<<j<<" = ";
if (neg==true)
{
cout<<"-1 x ";
}
for (i=0;i<to;i++)
{
cout<<num[i]<<" x ";
}
cout<<num[to]<<endl;
}



}


[/cpp]
why?i tried many cases, and it could run it properly.

[SilVer DirectXer]

your code is fail when input is 1

[raymond85]

Excuse me.....
I got TLE in this problem too.....
I tested my program with about 400 random 9-digits numbers.
I tested my program with 2147483640 to 2147483647.
I tested my program with some large primes.
I also tested my program with some small numbers.
My program is giving out an output immediately after i input a number but still I got TLE on the judge.....can anyone help? confused...

[raymond85]

finally i got AC...... i add a break in a loop so that it will stop looping once it finds a prime factor.....

btw the time is quite unsatisfactory.....wonder if there's anyway to improve the speed......