583 - Prime Factors

[unaben]

Hello everyone! I am getting WA with my code. I tried all the possible input that I could think of, but nothing. Could someone plz take a look at my code and give me a hint where the mistake is?

Here is the code:

#include<iostream>

using namespace std;

long int*primes = new long int[10000];
int pr=1;

void handle(long long int num)
{
bool ok = true;
long long int backup = num;
if(num<0)
backup = num * (-1);
cout<<num<<" = ";
if(num<0)
cout<<"-1 x ";
bool first = true;
for(int i=1; ok and i<pr; i++)
{
if(backup%primes[i]==0 and backup>1)
{
while(backup%primes[i]==0)
{
if(first==false)
cout<<" x ";
cout<<primes[i];
first = false;
backup/=primes[i];

}

}
if(primes[i]>backup)
ok = false;
}
if(ok)
cout<<backup;
cout<<endl;
}

int main()
{

bool *array = new bool[50000];
primes[0]=1;
long int n =50000;
array[0]=0;
array[1]=1;
for(int i=2; i<n; i++)
array[i]=1;
int p = 2;
while(p*p<=n)
{
primes[pr]=p;
pr++;
int j = p*p;
while(j<=n)
{
array[j]=0;
j+=p;
}
bool ok = true;
for(int k=p+1; ok and k<=n; k++)
{
if(array[k]==1)
{
ok = false;
p++;
}
else
p++;
}
}
for(int t=p+1; t<=n; t++)
{
if(array[t]==1)
{
primes[pr]=t;
pr++;
}
}
long long int num;
while(cin>>num and num!=0)
{
if(num ==1)
cout<<"1 = 1"<<endl;
else if(num==-1)
cout<<"-1 = -1 x 1"<<endl;
else
handle(num);
}
delete []array;
delete[]primes;
}

Thanx!

[rvarshne]

Hi,
Can anyone tell me why this algorithm gives TLE
Thanks

Code: Select all

#include <stdio.h>
#include <math.h>

int factors[46342];
unsigned int primes[46342];

void fillPrimes()
{
       for(int i = 0; i < 46342; i++)
       {
               primes[i] = 1;
       }

       for(unsigned int i = 2; i < 46342; i++)
       {
               if(primes[i] == 1)
               {
                       for(unsigned long long j = i * i; j < 46342; j += i)
                       {
                               primes[j] = 0;
                       }
               }
       }
}

int isPrime(long int n)
{
   int value = (int)sqrt((double)n);
   for(int i = 2; i <= value; i++)
   {
      if(primes[i] == 1)
      {
         if(n % i == 0)
         {
            return 0;
         }
      }
   }

   return 1;
}

int main()
{
       fillPrimes();

       long int n;
       while(scanf("%ld", &n) > 0)
       {
               if(n == 0)
               {
                       break;
               }

               int flag = 0;
               if (n < 0)
               {
                       n = -n;
                       flag = 1;
               }

               if(n == 1)
               {
                       if(flag == 1)
                       {
                               printf("-1 = -1\n");
                       }
                       else
                       {
                               printf("1 = 1\n");
                       }
               }
               else if(isPrime(n) == 1)
               {
                       if(flag == 1)
                       {
                               printf("-%ld = -1 x %ld\n", n, n);
                       }
                       else
                       {
                               printf("%ld = %ld\n", n, n);
                       }
               }
               else
               {
                       for(int i = 0; i < 46342; i++)
                       {
                               factors[i] = 0;
                       }

                       int x = n;
                       for(int i = 2; i < 46342; i++)
                       {
                     if(primes[i] == 1)
                     {
                               while(x % i == 0)
                               {
                                       factors[i]++;
                                       x = x / i;
                               }
                     }
                       }

                       if(flag == 1)
                       {
                               printf("-%ld = -1", n);
                       }
                       else
                       {
                               printf("%ld =", n);
                       }

                       int printFlag = 0;
                       for(int i = 2; i < 46342; i++)
                       {
                               if(flag == 0 && printFlag == 0 && factors[i] != 0)
                               {
                                       for(int j = 0; j < factors[i]; j++)
                                       {
                                               if(j != factors[i] - 1)
                                               {
                                                       printf(" %ld x", i);
                                               }
                                               else
                                               {
                                                       printf(" %ld", i);
                                               }
                                       }

                                       printFlag = 1;
                               }
                               else
                               {
                                       for(int j = 0; j < factors[i]; j++)
                                       {
                                               printf(" x %ld", i);
                                       }
                               }
                       }
                       printf("\n");
               }
       }
       return 0;
}


[Spykaj]

Input:

Code: Select all

200000002
420010962

Output:

Code: Select all

200000002 = 2 x 17 x 5882353
420010962 = 2 x 3 x 7 x 10000261

Your output:

Code: Select all

200000002 = 2 x 17
420010962 = 2 x 3 x 7

[rskvijay]

Hi ,
i have submitted this prime factors 583 problem 3 times n got time limit exceeded
here are some input n output with the time taken for my program execution..

Code: Select all

$ cat > input
200000002
420010962
1445454
15454
-154515
-8845
-1547
46337
92674
1073741824
2147483647
2147483646
-2147483647
-2147483646
0
ctl-d
$ time ./a.out < input
200000002 = 2 x 17 x 5882353
420010962 = 2 x 3 x 7 x 10000261
1445454 = 2 x 3 x 3 x 131 x 613
15454 = 2 x 7727
-154515 = -1 x 3 x 5 x 10301
-8845 = -1 x 5 x 29 x 61
-1547 = -1 x 7 x 13 x 17
46337 = 46337
92674 = 2 x 46337
1073741824 = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2
2147483647 = 2147483647
2147483646 = 2 x 3 x 3 x 7 x 11 x 31 x 151 x 331
-2147483647 = -1 x 2147483647
-2147483646 = -1 x 2 x 3 x 3 x 7 x 11 x 31 x 151 x 331

real    0m0.060s
user    0m0.060s
sys     0m0.000s
$


now guyz if someone post the time taken for your program for the above input i would be thankful..

here is my c++ code

Code: Select all

 #include<iostream>
 #include<math.h>
 #include<limits.h>

 using namespace std;

 bool isprime(int n)
{
 if( n == 1 )
        return 0;
 for( int i=2 ; i<=sqrt(n) ; i++ )
        if( n%i == 0 )
                return 0;
 return 1;
}

 int main()
{
 int prime[5000] , end = 0;
 for( int i=1 ; i<=sqrt(INT_MAX) ; i++ )
        if( isprime(i) )
                prime[end++] = i;
 while(1)
 {
        int n;
        int fact[1000000];
        int ind = 0;
        cin >> n;
        if( n == 0 )
                break;
        int num = abs(n);
        for( int i=0 ; prime[i]<=sqrt(abs(n)) ; i++ )
        {
                int l = abs(n)/prime[i] ;
                for( ; ( num%prime[i] == 0 ) ; num /= prime[i] )
                        fact[ind++] = prime[i];
                if( num%l == 0 )
                 if( isprime(l) )
                   for(  ; num%l == 0 ; num /= l )
                        fact[ind++] = l;
        }
        if( n < 0 )
                cout << n << " = -1 x";
        else
                cout << n << " =";
        for( int i=0 ; i<ind ; i++ )
        {
                cout << " " << fact[i] ;
                if( i != ind-1 )
                        cout << " x";
        }
        if( isprime(num) )
        {
                if( ind != 0 )
                        cout << " x " << num ;
                else
                        cout << " " << num ;
        }
        cout << "\n" ;
 }
 return 0;
}


[rio]

Code: Select all

        for( int i=0 ; prime[i]<=sqrt(abs(n)) ; i++ )
        {
                int l = abs(n)/prime[i] ;
                for( ; ( num%prime[i] == 0 ) ; num /= prime[i] )
                        fact[ind++] = prime[i];
                if( num%l == 0 )
                 if( isprime(l) )
                   for(  ; num%l == 0 ; num /= l )
                        fact[ind++] = l;
        }


This main loop is too slow.

[newton]

i cant understand why i'm getting SIGNAL 8 (floating point exception)?
please check my code.

Code: Select all


#include <stdio.h>
#include <string.h>
#include <math.h>


int prime[10000];
int main()
{

   int i,j,array[10000];
   long int num;
   memset(prime,0,sizeof(prime));
   for(i=2;i<=10000;i++)
   {
      for(j=2;i*j<=10000;j++)
         prime[i*j]=1;
   }

   j = 0;
   for(i=2;i<=10000;i++)
      if(prime[i]==0)
         array[j++]=i;

   while(scanf("%ld",&num)!=EOF)
   {
      long temp = num;
      for(i=0 ; array[i]<=temp ; i++)
      {
         if((num % array[i] == 0) && num!=1)
         {
            while(num % array[i] == 0 && num!=1 && num)
            {
               printf("%d\n",array[i]);
               num/=array[i];
            }
         }
      }
   }
   return 0;
}



[nymo]

to Newton,
I 've just skim through your code...

From your code, I suppose you are trying to find out the primes upto 10000; but why 10000? input range is -2^31 to 2^31 (not inclusive); you should have gone upto at least the squre root of 2^31.

Code: Select all

 for(i=2;i<=10000;i++)
   {
      for(j=2;i*j<=10000;j++)
         prime[i*j]=1;
   }


declaring

Code: Select all

int prime[10000];


you have index 0-9999; you are allowing 10000 to be indexed.

[newton]

i have chaned it but got signal 8 (RE)

Code: Select all

#include <stdio.h>
#include <math.h>
#include <string.h>

int prime[100001],array[100001];

void set_prime()
{
   int i,j;
   memset(prime,0,sizeof(prime));
   for(i=2;i<=100000;i++)
   {
      for(j=2;i*j<=sqrt(100000);j++)
         prime[i*j]=1;
   }

   j = 0;
   for(i=2;i<=100000;i++)
      if(prime[i]==0)
         array[j++]=i;
   return;
}


void main()
{
   long num,i;
   set_prime();
   while(scanf("%ld",&num) && num)
   {
      printf("%ld = ",num);
      if(num<0)
      {
         if(num==-1)
         printf(" -1\n");
         else
         {
            printf(" -1 x");
            num *= -1;
         }
      }
      while(num!=1)
      {
         for(i=0;num!=1;i++)
         {
            if(num%array[i]==0 && num!=1)
            {
               while(num%array[i]==0 && num!=1)
               {
                  num /= array[i];
                  if(num == 1)
                     printf(" %d",array[i]);
                  else
                     printf(" %d x",array[i]);

               }
            }
         }
      }
      printf("\n");
   }
}




[nymo]

to Newton,

Code: Select all

for(i=0;num!=1;i++)
         {
            if(num%array[i]==0 && num!=1)
            {
               while(num%array[i]==0 && num!=1)
               {
                  num /= array[i];
                  if(num == 1)
                     printf(" %d",array[i]);
                  else
                     printf(" %d x",array[i]);

               }
            }


In this portion index i can overflow to access outside the array.

Code: Select all

void set_prime()
{
   int i,j;
   memset(prime,0,sizeof(prime));
   for(i=2;i<=100000;i++)
   {
      for(j=2;i*j<=sqrt(100000);j++)
         prime[i*j]=1;
   }

   j = 0;
   for(i=2;i<=100000;i++)
      if(prime[i]==0)
         array[j++]=i;
   return;
}


does this code generate primes that you need for this problem ???

[newton]

dear nymo i have changed everything you told
but still got RE

Code: Select all

#include <stdio.h>
#include <math.h>
#include <string.h>

int prime[100001],array[100001];


void set_prime()
{
   int i,j;
   memset(prime,0,sizeof(prime));
   for(i=2;i<=100000;i++)
   {
      for(j=2;i*j<=sqrt(100000);j++)
         prime[i*j]=1;
   }

   j = 0;
   for(i=2;i<=100000;i++)
      if(prime[i]==0)
         array[j++]=i;
   return;
}


void main()
{
   long num,i;
   set_prime();
   while(scanf("%ld",&num) && num)
   {
      printf("%ld = ",num);
      if(num<0)
      {
         if(num==-1)
         printf(" -1\n");
         else
         {
            printf(" -1 x");
            num *= -1;
         }
      }
      while(num!=1)
      {
         for(i=0;num!=1;i++)
         {
            if(num%array[i]==0 && num!=1)
            {
               while(num%array[i]==0 && num!=1)
               {
                  num /= array[i];
                  if(num == 1)
                     printf(" %d",array[i]);
                  else
                     printf(" %d x",array[i]);

               }
            }
         }
      }
      printf("\n");
   }
}


[Jan]

It seems that your code has some problems. Your are thinking that you can always return to 1 (num). But what if the input is like 1999957, which is a prime greater than 100000.

Code: Select all

while(num!=1)
      {
         for(i=0;array[i]*array[i]<=num;i++)
         {
            if(num%array[i]==0)
            {
               while(num%array[i]==0)
               {
                  num /= array[i];
                  if(num == 1)
                     printf(" %d",array[i]);
                  else
                     printf(" %d x",array[i]);

               }
            }
         }
         if(num>1)
             printf(" %d",num);
      }

Hope these help.

[pradeepr]

help me please...

[mf]

Try 2147117569.
Your program outputs an extra " x 1" at the end, which it shouldn't do.

[pradeepr]

thanks...

its working now..and it was accepted...

[Deny Sutani]

I got CE with this code

Code: Select all

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

long bil_prima[10000]={prime number between 1-50000}

int prime(long angka)
{
    int prime;
 
    if(angka==1) prime = 0;
    if(angka==2) prime = 1;
    if(angka==3) prime = 1;
    else
    for(long  j=2; j<=sqrt(angka);j++)
    {
        if(angka%j==0) {prime=0;break;}
        else prime =1;
    }
    return prime;
}

int main()
{
   

   
    long angka,temp, x;
    //prima();
    while(scanf("%ld",&angka) && angka !=0)
    {
       
        printf("%ld = ",angka);
        x = 0;
        if(angka < -1)
        {
            printf("-1 x ");
            angka = angka * -1;
            //printf("%ld \n",angka);
        }
       
        while(angka>1)
        {
            if(prime(angka))
            {
                printf("%ld\n",angka);
                angka/=angka;
            }
            if(angka%bil_prima[x]==0)
            {
                printf("%ld ", bil_prima[x]);
                angka/=bil_prima[x];
                if (angka > 1) printf("x ");
            }
            else bil_prima[x++];
        }   
    }
    return 0;
}


What wrong with my code?