### Re: 160 - Factors and Factorials

Posted:

**Mon Jul 19, 2010 1:11 am**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:
The WA code that generates the answer at the begining:

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[100];
void primeFactorization(int input)
{
for(int j=2; j<=input; j++)
{
int number = j;
while ((number % 2) == 0)
{
primesFactors[2]++;
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;
}
```

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[100][100];
int result[100];
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][2]++;
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;
}
```