## 583 - Prime Factors

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

Moderator: Board moderators

### 583 - WA Prime Factors

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!
unaben
New poster

Posts: 12
Joined: Mon Jul 10, 2006 10:47 pm

### 583 TLE

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;}`
rvarshne
New poster

Posts: 3
Joined: Tue Dec 05, 2006 11:02 pm

Input:
Code: Select all
`200000002420010962`

Output:
Code: Select all
`200000002 = 2 x 17 x 5882353420010962 = 2 x 3 x 7 x 10000261`

Your output:

Code: Select all
`200000002 = 2 x 17420010962 = 2 x 3 x 7`

Spykaj
New poster

Posts: 47
Joined: Sun May 21, 2006 12:13 pm

### 583.. why TLE ???

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 > input200000002420010962144545415454-154515-8845-15474633792674107374182421474836472147483646-2147483647-21474836460ctl-d\$ time ./a.out < input200000002 = 2 x 17 x 5882353420010962 = 2 x 3 x 7 x 100002611445454 = 2 x 3 x 3 x 131 x 61315454 = 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 1746337 = 4633792674 = 2 x 463371073741824 = 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 22147483647 = 21474836472147483646 = 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 331real    0m0.060suser    0m0.060ssys     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;}`
rskvijay
New poster

Posts: 3
Joined: Fri Mar 23, 2007 5:57 pm

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.

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

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;}`

newton
Experienced poster

Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh

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.
regards,
nymo
nymo
Experienced poster

Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

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");   }}`

newton
Experienced poster

Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh

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 ???
regards,
nymo
nymo
Experienced poster

Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

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");    } }`

newton
Experienced poster

Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh

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.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh

### WA... somebody plz help me out!!

help me please...
Last edited by pradeepr on Wed May 30, 2007 8:28 am, edited 1 time in total.
pradeepr
New poster

Posts: 21
Joined: Fri May 25, 2007 11:52 am
Location: India

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

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

### thanks.. its working!!

thanks...

its working now..and it was accepted...
pradeepr
New poster

Posts: 21
Joined: Fri May 25, 2007 11:52 am
Location: India

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?
Deny Sutani
New poster

Posts: 6
Joined: Fri Jun 01, 2007 7:20 am

PreviousNext

Return to Volume V

### Who is online

Users browsing this forum: No registered users and 0 guests