PNOI 2k8 Problem A: A Simple Task

Problems from PNOI2008

Type: mathematics
Difficulty: easy

The first thing that came to mind in looking at this problem was "prime factorization".

Every positive integer has a unique prime factorization, and there is an algorithm for outputting the prime factors of a number n:

p = 2;
while (p * p <= n) {
  if (n % p == 0) {
    output p;
    n /= p;
  } else p ++;  
}

Simply put, if the current prime number being considered divides the number n, divide n by p (and output p), otherwise go to the next prime number, until what remains is prime.

There are some details of the loop that need noting: p does go through non-prime numbers, like 4, but, at that point in time (what is left of) n cannot be divisible by 4, otherwise, it would have been divisible by 2, and then divided by 2 before p becomes 4; the loop condition basically ensures that, if it is not met, the value in n is a prime value, but how?

Those familiar with the Sieve of Eratosthenes know that you can determine the primes in the range of 2 to n by marking the lowest uncrossed number as prime, crossing out all its multiples, then repeating until no more values can be crossed out. Experience will tell you that once you cross out the multiples of the largest prime less than or equal to the square root of n, the remaining uncrossed numbers are all prime.

This is because if one of the numbers between the square root of n and n was composite, say c, it would have to be a multiple of a number also in the range, say p < c, otherwise it would have been crossed out. But c has to be at least p * p, and p * p is greater than n, so that's not possible.

That explains the prime factorization algorithm, but how do you solve problem A?

We simply divide n by 2 as many times as possible, counting: whatever remains is odd.

p = 0;
while (n % 2 == 0) {
  p ++;
  n /= 2;
}
output n, p;