ACM (UVa) : 160


Calculate the factorial of given number n
and then find the prime factor of factorial n (n!)

for example:
5 ! = 120 = 2 * 2 * 2 * 3 * 5
6 ! = 720 = 2 * 2 * 2 * 2 * 3 * 3 * 5

this destructive process should not be implemented ..
rather, we can find a far better way to do that, lets see
5 ! = 120 = 5 * 4 * 3 * 2

write a procedure that can count prime factors of a given number

prime_factor (5) + prime_factor (4) + prime_factor (3) + prime_factor (2) = prime_factor (5!) = prime_factor (120)

similarly, 6 ! = 720 = 6 * 5 * 4 * 3 * 2

prime_factor (6) + prime_factor (5) + prime_factor (4) + prime_factor (3) + prime_factor (2) = prime_factor (6!) = prime_factor (720)

prime_factor of (N)
continue while (N > 1) {
continue while (N % prime = 0)
N /= prime;
prime = Next_prime ();
}

// u need to calculate just these prime factors,
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

// u must not print such prime factors position which frequency is zero

output format:

1. Number N have to be printed right justified of width 3
2. Each of occurrence will be printed again, right justified of field width 3
3. if there r more than 15 occurrence in one line then u have to print a newline and start to print next occurrence with a field width 6

#include

int main ()
{
long n, i, flag, count, j, save;
long b [] = {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};

while (scanf (“%ld”, &n)) {

if (n == 0)
return 0;

save = n;

long a [25] = {0};

while (n != 1) {
i = n;
j = 0;

while (i > 1) {
count = 0;
while (i % b [j] == 0) {
i /= b [j];
count++;
}
a [j] += count;
j++;
}

n–;
}

// output

for (i = 24; i >= 0; i–) {
if (a [i] != 0)
break;
}
j = i;

printf(“%3ld! =”, save);
if (j >= 15)
flag = 0;
else
flag = 15;
for (i = 0; i <= j; i++) { printf("%3ld", a [i]); flag++; if (flag == 15) printf("\n%6c",' '); } printf("\n"); } return 0; }[/sourcecode]

Critical input:
1
2
3
4
6
7
8
9
10
100
99
98
66

Critical output:
160_output

Advertisements

3 thoughts on “ACM (UVa) : 160

  1. Hello
    i would really be grateful if you can tell me why do i get WA in this code 😦
    UVA-160 … till now i submitted 6 times with wrong answer :(, and i checked everything, so plz help 🙂 thanks in advance 🙂

    #include<iostream>
    #include<iomanip>
    using namespace std;
    int nPow[100];
    bool check[10];
    
    void counter(int num)
    {
        for(int i=2 ; i*i<=num ; i++)
        {
             while(num%i == 0)
             {
                  num /= i;
                  nPow[i]++;
                  check[i]=1;
             }
        }
        
        if(num>1)
        {
             nPow[num]++;
             check[num]=1;
        }
    }
    int main()
    {
        bool checkPrime=true;
        int num;
        char o='!', s=' ' , e='=';
        while(cin>>num)
        {
              if(num == 0) 
              {
                     system("pause");
                     return 0;
              }
              memset(nPow,0,sizeof(nPow));
              memset(check,0,sizeof(check));         
              int line=0;
              for(int i=2 ; i<=num ; i++)
              counter(i);
              cout<<setw(3)<<num<<o<<s<<e;
              for(int i=2 ; i<=num ; i++)
              {
                   if(line==15)
                   {
                         cout<<endl<<setw(6)<<" "; 
                         line=0; 
                   }
                   if(check[i]==1){cout<<setw(3)<<nPow[i]; line++;}
              }
        cout<<endl;
        }
    }
    
    
  2. @Ali El Khateeb
    hi there
    would you please mail me the code, tausiq19@gmail.com
    thanks 🙂
    Depending on the nature, some of IDE (s) need
    system(“pause”);
    for example, Dev C++
    this is not the case for GNU C++, which is being used by Uva online Judge.
    So, u should not use
    system(“pause”);
    or, make it comment before submission
    Another thing,
    your program gives an extra space after the output of
    48, 49, 50, 51 and 52

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s