Prova algoritmos avançados

USP-ICMC-SCC - Ciências de Computação Substitutiva da Prova 2 - 16 a 19/11/2010

Algoritmos Avançados - SCC-0210
Prof. João Luís - Monitores: Roberto de Medeiros (PAE) e Raphael Ferras Obs.: A prova é individual. O Boca estará aberto entre 16 e 19/11, das 19 às 23h00. (3) 1.

Prime Factors:

An integer g > 1 is said to be prime if and only if its only positive divisors are itself and one (otherwise it is said to be composite). For example, the number 21 is composite; the number 23 is prime. Note that the decomposition of a positive number g into its prime factors, i.e., g = f1 × f2 × · · · × fn is unique if we assert that fi > 1 for all i and fi ≤ fj for i < j.

One interesting class of prime numbers are the so-called Mersenne primes which are of the form 2p − 1. Euler proved that 231 − 1 is prime in 1772 – all without the aid of a computer. • Input: The input will consist of a sequence of numbers. Each line of input will contain one number g in the range −231 < g < 231 , but different of -1 and 1. The end of input will be indicated by an input line having a value of zero. • Output: For each line of input, your program should print a line of output consisting of the input number and its prime factors. For an input number g > 0, g = f1 × f2 × · · · × fn , where each fi is a prime number greater than unity (with fi ≤ fj for i < j), the format of the output line should be g = f1 x f2 x . . . x fn When g < 0, if | g |= f1 × f2 × · · · × fn , the format of the output line should be g = -1 x f1 x f2 x . . . x fn • Sample Input
-190 -191 -192 -193 -194 195 196 197 198 199 200 0

Página 1 de 4

Veja a próxima página. . .

ICMC-USP Sub P2, 16 a 19/11/2010 SCC-0210 (continuação) • Sample Output
-190 = -1 -191 = -1 -192 = -1 -193 = -1 -194 = -1 195 = 3 x 196 = 2 x 197 = 197 198 = 2 x 199 = 199 200 = 2 x x x x x x 5 2 2 x 5 x 19 191 2 x 2 x 2 x 2 x 2 x 2 x 3 193 2 x 97 x 13 x 7 x 7

3 x 3 x 11 2 x 2 x 5 x 5

(3) 2.

LC-Display:

A friend of you has just