583 - Prime Factors

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Post by Morning »

My outputs are all right :-?
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by 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 !! :D

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Post by Morning »

:oops: it helps a lot,i've gotten AC
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

Wei
New poster
Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm
Contact:

583~~with WA~~~><"

Post by 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
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by 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
New poster
Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm
Contact:

Post by Wei »

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

narsys
New poster
Posts: 5
Joined: Sat Jun 04, 2005 6:34 am

583 (prime factor prob) TLE

Post by 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<<" x ";
}

cout<<answer<<endl;
}
}
Last edited by narsys on Sun Jun 19, 2005 4:59 am, edited 1 time in total.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by 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
New poster
Posts: 5
Joined: Sat Jun 04, 2005 6:34 am

excuse me

Post by 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<<" x ";
}

cout<<answer<<endl;
}
}

Fuad Hassan_IIUC(DC)
New poster
Posts: 18
Joined: Fri Jan 07, 2005 9:35 pm
Location: Bangladesh

583~~TLE!!!~~

Post by Fuad Hassan_IIUC(DC) »

Why am i getting TLE???? :o
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<<' ';
if(i<k+1)
cout<<'X'<<' ';
}
cout<<endl;

}
}
return 0;
}
fuad

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by 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. :D

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

583 Why Output Limit Exceeded ??

Post by 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
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince »

Hi unuguntsai

I think for this input you are getting OLE
INPUT
2147483647

Thanks :)
MAP

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

Post by unuguntsai »

My Output

2147483647 = 2147483647

is it OLE ??

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by 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 :wink:

Post Reply

Return to “Volume 5 (500-599)”