## 160 - Factors and Factorials

Moderator: Board moderators

il_demente
New poster
Posts: 1
Joined: Mon Jul 19, 2010 12:50 am

### Re: 160 - Factors and Factorials

My problem here is more like an inquiry. You see i wrote a code that calculated the prime factors of all numbers at the beginning of the main function and starts taking input and outputs the related answer. When i submitted this code i got WA i checked the code for any possible reason of getting the WA but i couldn't find one thing that would justify this WA. So after i gave up debugging, i deleted all the code and started a new one where i calculated the prime factors of each number that is inputed and i got AC.

It rose my suspicion so i tried to check for the output of both codes that i wrote so i generated all the numbers from 2 to 100 as stated in the problem set and saved the output of both codes in an external file. I compared the output of both files using a program i have and i found that the were the same no extra white spaces, nothing. They were the same

My question is what is the reason that the judge rejected the first code, yet it accepted the other code even though they generate the same output for the stated input.

the AC code:

Code: Select all

``````#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;

int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int primesFactors;
void primeFactorization(int input)
{
for(int j=2; j<=input; j++)
{
int number = j;
while ((number % 2) == 0)
{
primesFactors++;
number = number / 2;
}
int i = 3;

while (i*i <= (number) + 1)
{
if ((number % i) == 0)
{
primesFactors[i]++;
number /= i;
}
else i = i + 2;
}
if (number > 1)
primesFactors[number]++;
}
}
int main()
{
int input;
while(cin >> input && input)
{
memset(primesFactors, 0, sizeof primesFactors);
primeFactorization(input);
printf("%3ld! =",input);
for(int j=0, c=0; j<25; j++, c++)
{
if(primes[j]>input)
break;
if(c%15==0 && c)
printf("\n%6c",' ');
printf("%3d",primesFactors[primes[j]]);
}
printf("\n");
}
return 0;
}

``````
The WA code that generates the answer at the begining:

Code: Select all

``````#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;

int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int pFactors;
int result;

void primeFactorization()
{
memset(pFactors, 0, sizeof(int) * 100 *100 );
memset(result, 0, sizeof(int) * 100);
int number;
for(int j=2; j<=100; j++)
{
number = j;
while ((number % 2) == 0)
{
pFactors[j]++;
number /= 2;
}

int i = 3, root = sqrt((double)number) +1;
while (i <= root)
{
if ((number % i) == 0)
{
pFactors[j][i]++;
number /= i;
}
else i += 2;
}
if (number > 1)
pFactors[j][number]++;
}
}

int main()
{
int input;
primeFactorization();
while(cin >> input && input)
{

memset(result, 0, sizeof result);

//These 2 loops iterate through all the primes which are factors of
//the factorial of the input and add them to the result array
for(int i=0; i<25; i++)
for(int j=2; j<=input; j++)
result[primes[i]]+= pFactors[j][primes[i]];

printf("%3ld! =",input);
for(int j=0, c=0; j<25; j++, c++)
{
if(primes[j]>input)
break;
if(c%15==0 && c)
printf("\n%6c",' ');
printf("%3d",result[primes[j]]);
}
printf("\n");

}
return 0;
}
``````

tuner
New poster
Posts: 1
Joined: Sun Apr 24, 2011 6:48 pm

### 160 - Factors and Factorials (WA)

my code below
i still cannot find where get wrong
anyone can help me or give me some tips
or some key test case
point what's wrong with my code
THX

Code: Select all

``````#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

int main ()
{
int n;
while ( cin >> n )
{
if ( n == 0 )   return 0;
int fac[n + 1];
for ( int i = 2; i <= n; i++ )
fac[i] = 0;
for ( int i = n; i >= 2; i-- )
{
for ( int j = 2; j <= n; j++ )
{
int k = i;
while ( k % j == 0 )
{
fac[j]++;
k /= j;
}
}
}
cout << setw(3) << right << n << "! =";
for ( int i = 2; i <= n; i++ )
{
if ( i == 2 || i == 3 || i == 5 || i == 7 || i == 11 ||
i == 13 || i == 17 || i == 19 || i == 23 || i == 29 ||
i == 31 || i == 37 || i == 41 || i == 43 || i == 47 ||
i == 53 || i == 59 || i == 61 || i == 67 || i == 71 ||
i == 73 || i == 79 || i == 83 || i == 89 || i == 97 )
{
cout << setw(3) << fac[i];
}
if ( i == 47 )
{
cout << endl << setw(6) << " ";
}
}
cout << endl;
}
return 0;
}
``````

wetcat
New poster
Posts: 1
Joined: Sun Jun 19, 2011 9:21 am

### 160 getting WA

my output is right,but why i am getting WA???pls help me...

int prime={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int m,factor_counter;

int find_prime_factor(int a)
{
if(a==1)
return 0;

else if(a%prime[m]==0)
{
factor_counter[prime[m]]++;
find_prime_factor(a/prime[m]);
}
else
{
m++;
find_prime_factor(a);
}

}

int main()
{

int n,temp,i,j,count;
while(cin>>n && n!=0)
{

for(i=0;i<101;i++)
factor_counter=0;
for(i=2;i<=n;i++)
{
m=0;
find_prime_factor(i);
}
cout<<setw(3)<<n<<"! =";
for(int x=3, i=2,count=0;i<99;i++)
{

if(count==15)
{
cout<<endl;
count=0;
x=9;
}
if(factor_counter>0)
{
cout<<setw(x)<<factor_counter;
x=3;
count++;
}
}

cout<<endl;
}
return 0;
}

bloodytears67
New poster
Posts: 2
Joined: Mon Jan 23, 2012 11:58 pm

### 160 runtime error!

It crashes after 96 Code: Select all

``````#include <stdio.h>

int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};

int main()
{
int n,i;

while ((scanf("%d",&n))==1)
{
if (n==0) break;

else
{
printf("%3d! =",n);
int count,temp;
for (i=0; primes[i]<=n; i++)
{
count = 0;
temp = n;
while (temp>0)
{
temp/=primes[i];
count+=temp;
}
if (i == 15) printf("\n%9d",count);
else printf("%3d",count);

}

printf("\n");
}
}

return 0;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 160 runtime error!

Check input and AC output for thousands of problems on uDebug!

bloodytears67
New poster
Posts: 2
Joined: Mon Jan 23, 2012 11:58 pm

### Re: 160 runtime error!

thanks brianfry713 it worked happyson10
New poster
Posts: 20
Joined: Wed Nov 14, 2012 11:20 pm

### Presentation error on 160

The code was removed after getting AC
Last edited by happyson10 on Thu Jan 03, 2013 12:09 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: Presentation error on 160

you've got an extra space after the =
Check input and AC output for thousands of problems on uDebug!

happyson10
New poster
Posts: 20
Joined: Wed Nov 14, 2012 11:20 pm

### Re: Presentation error on 160

oh, got it, thanks a lot

gr81
New poster
Posts: 46
Joined: Wed Sep 26, 2012 7:52 pm

### Re: Presentation error on 160

getting WA, in this case, but passed all my test case...please have a look ..

AC now.

thanks...
Last edited by gr81 on Thu Jan 10, 2013 4:04 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: Presentation error on 160

Don't print an extra blank line at the end.
Check input and AC output for thousands of problems on uDebug!

gr81
New poster
Posts: 46
Joined: Wed Sep 26, 2012 7:52 pm

### Re: Presentation error on 160

I removed the new line at the end, but still getting WA.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: Presentation error on 160

Input

Code: Select all

``````47
48
0``````
Correct output:

Code: Select all

`````` 47! = 42 21 10  6  4  3  2  2  2  1  1  1  1  1  1
48! = 46 22 10  6  4  3  2  2  2  1  1  1  1  1  1``````

Code: Select all

`````` 47! = 42 21 10  6  4  3  2  2  2  1  1  1  1  1  1

48! = 46 22 10  6  4  3  2  2  2  1  1  1  1  1  1

``````
Check input and AC output for thousands of problems on uDebug!

gr81
New poster
Posts: 46
Joined: Wed Sep 26, 2012 7:52 pm

### Re: Presentation error on 160

thanks brian..
that was kewl input.

techbd123
New poster
Posts: 14
Joined: Tue Aug 06, 2013 3:42 pm

### Re: Presentation error on 160

Why getting WA and printing a newline it's PE???

My code is here. http://pastebin.com/mYH6gGcD