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==0 and backup>1)
{
while(backup%primes==0)
{
if(first==false)
cout<<" x ";
cout<<primes;
first = false;
backup/=primes;

}

}
if(primes>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=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?