## 583 - Prime Factors

Moderator: Board moderators

unaben
New poster
Posts: 12
Joined: Mon Jul 10, 2006 10:47 pm

### 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==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
New poster
Posts: 3
Joined: Tue Dec 05, 2006 11:02 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;
}
``````

Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm
Input:

Code: Select all

``````200000002
420010962``````
Output:

Code: Select all

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

Code: Select all

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

rskvijay
New poster
Posts: 3
Joined: Fri Mar 23, 2007 5:57 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 > 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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

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
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:
i cant understand why i'm getting SIGNAL 8 (floating point exception)?

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
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)
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

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:
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
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)
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

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:
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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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

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

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

Last edited by pradeepr on Wed May 30, 2007 8:28 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Try 2147117569.
Your program outputs an extra " x 1" at the end, which it shouldn't do.

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

### thanks.. its working!!

thanks...

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

Deny Sutani
New poster
Posts: 6
Joined: Fri Jun 01, 2007 7:20 am
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?