583 - Prime Factors

[Morning]

My outputs are all right :-?

[Ghust_omega]

Hi !! Morning this WA was hard to find I'm sure that is a stupid thing this is the I/O that I use
input :

Code: Select all

46337
92674
0


your ouputs

Code: Select all

46337 = 46337 x 1
92674 = 2 x 46337 x 1



My ouput

Code: Select all

46337 = 46337
92674 = 2 x 46337


Hope it helps
Keep posting !!

[Morning]

it helps a lot,i've gotten AC

[Wei]

Well~~I don't know where is wrong~~
Can anyone help me????

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(void)
{
  int n,i,t,m,a[4800],k;
  k=0;
  for(i=2;i<=46342;i++)
  {
    t=0;
    n=2;
    while(n<=sqrt(i)&&t==0)
    {
        if(i%n==0)
            t=1;
        else
            n++;
    }
    if(t==0)
    {
        k++;
        a[k]=i;
    }
  }
  scanf("%d",&n);
  while(n!=0)
  {
    t=0;
    printf("%d = ",n);
    if(n==1)
        printf("%d",n);
    if(n<0)
    {
        printf("-1");
        t=1;
        n=-n;
    }
    i=1;
    m=n;
    while(n!=1&&a[i]<=sqrt(m)&&i<=4792)
    {
        if(n%a[i]==0)
        {
            n=n/a[i];
            if(t!=0)
                printf(" * %d",a[i]);
            else
                printf("%d",a[i]);
            t++;
        }
        else
            i++;
    }
    if(n!=1)
    {
      if(t==0)
        printf("%d",n);
      else
        printf(" * %d",n);
    }
    printf("\n");
    scanf("%d",&n);
  }
  system("PAUSE");
  return 0;
}


[mohiul alam prince]

Hi
i have just changed x instead of *
and
i don't use // system("PAUSE");
that's why u have got AC

MAP

[Wei]

Well~~Thx a lot ~~~
I got AC then ~~~

[narsys]

hey I use this simple and clear algorithm but get TLE (Can I use array with prime numbers to get AC?) I don't want this solution.Is there another way other that.
Excuse me it is not correct I send the correct one in third post
#include <iostream>

using namespace std;


int main()
{

int num;
int number;
int count,i;
bool prime=true;



while (cin>>num)
{
int answer[50];
number=num;
count = 1;
prime=true;

if(num<0)
{
answer[0] = -1;
number=number*(-1);

}
else
count=0;


while(number%2==0)
{
answer[count] = 2;
count++;
number/=2;
}

for(i=3;i*i<=number;i+=2)// bug is here
{
prime=true;
while(number%i==0)
{
answer[count] = i;
count++;
number/=i;
prime=false;
}

}



if(prime==true)
{
answer[count]=number;
count++;
}

cout <<num <<" = ";

for(i=0;i<count-1;i++)
{
cout<<answer[i]<<" x ";
}

cout<<answer[i]<<endl;
}
}

[neno_uci]

Check the problem input/output, your problem should at least be right for those samples and then try to send it, for input:

-190

problem output:
-190 = -1 x 2 x 5 x 19

your output:
-190 = -1 x 2 x 5

besides, as I see you process input until the eof is reached and it must be until you read a 0, hope this helps,

Yandry.

[narsys]

I had changed my code before sent it and it was uncorrect
here is a correct code
#include <iostream>


using namespace std;


int main()
{

int num;
int number;
int count,i;
bool prime=true;



while (cin>>num && num!=0)
{
int answer[50];
number=num;
count = 1;
// prime=true;

if(num<0)
{
answer[0] = -1;
number=number*(-1);

}
else
count=0;


while(number%2==0)
{
answer[count] = 2;
count++;
number/=2;
}

for(i=3;/*i*i*/ i<=number;i+=2)
{
// prime=true;
while(number%i==0)
{
answer[count] = i;
count++;
number/=i;
// prime=false;
}

}



/* if(prime==true)
{
answer[count]=number;
count++;
}*/

cout <<num <<" = ";

for(i=0;i<count-1;i++)
{
cout<<answer[i]<<" x ";
}

cout<<answer[i]<<endl;
}
}

[Fuad Hassan_IIUC(DC)]

Why am i getting TLE????
plz help me.
#include<stdio.h>
#include<iostream.h>
#include<math.h>
#define max 480000
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 isprime(int a)
{
long long m;
for(m=0;m<max;m++)
{
if(a==prmcol[m])
return 1;
}
return 0;
}
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;
flag=0;
for(m=0;m<max;m++)
fact[m]=0;
j=0;result=abs(input);k=0;
if(isprime(abs(input)))
{
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(isprime(result))
{
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;
}

[neno_uci]

I got this problem ACed without using the Sieve of E..., a good algorithm and small knowledge about prime numbers will do..., best wishes,

Yandry.

[unuguntsai]

I don't know why OLE ??

Code: Select all

#include <iostream.h>
#include <stdlib.h>

int main()
{
      long long int n , x ;
      long long int prime[4792] ;
      int i , Cprime , k , ans ;

      for( k=3 , Cprime=1 , prime[0]=2 ; k<46341 ; 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;
      }

      while( cin >> n && !cin.eof() && n != 0 )
      {
        cout << n << " = " ;
        ans = 0 ;
        if( n < 0 )
        {
          cout << "-1" ;
          x = 0 - n ;
          ans = 1 ;
        }
        else
          x = n ;
        for( i = 0 ; prime[i]*prime[i] <= x ; i++ )
        {
          while( x % prime[i] == 0 )
          {
            x /= prime[i] ;
            if( ans )
              cout << " x " << prime[i] ;
            else
            {
              cout << prime[i] ;
              ans = 1 ;
            }
          }
        }
        if( x != 1 )
        {
          if( ans )  cout << " x " ;
          cout << x ;
        }
        else if( ans == 0 )  cout << "1" ;
        cout << endl ;
      }
      return 0;
}

[mohiul alam prince]

Hi unuguntsai

I think for this input you are getting OLE
INPUT
2147483647

Thanks
MAP

[unuguntsai]

My Output

2147483647 = 2147483647

is it OLE ??

[angga888]

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