Title: Maior número primo na sequência de números granizo
Course: Introdução à Ciência de Computação - 2016 > Section: 18 November - 25 November

A sequência de números granizo é a sequência que começa com um número inteiro n. Se n é par, o seguinte número na sequência é resultado de dividir n por 2. Se n é ímpar, o seguinte número na sequência é resultado de multiplicar n por 3 e adicionar 1. O processo é repetido com o novo valor de n, terminando no momento em que n=1. Por exemplo, a seguinte sequência de números granizo serão gerados para n=22:

22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5 , 16, 8, 4, 2,1

Escreva um algoritmo que, dado um número n, determine o maior número primo na sequência de números granizo iniciadas em n. No exemplo acima, dado o valor n=22, o maior número primo na sequência de números granizo será 17.

Dicas:

- O operador de resto em C é %, assim para calcular o resto de um número x entre 2  na variável resto deve ser escrita a linha: resto = x % 2;
- Números primos são os números naturais que têm apenas dois divisores diferentes: o 1 e ele mesmo. Lembre-se que 1 não é primo.

Entrada e Saída:

A entrada será constituída por um número inteiro n  maior do que 0 e menores que 10000. Cada linha no arquivo "input.txt" representará uma entrada para o programa.

Como saída, você deve imprimir dois números separados por um espaço em branco. O primeiro número será o valor de n, enquanto o segundo número será o maior número primo na sequência de números granizo iniciadas em n. Veja abaixo alguns exemplos de entrada/saída:

Exemplos de entrada | Saída para os exemplos de entrada
22 | 22 17
73 | 73 1619
77 | 77 29
9999 | 9999 33749