Decompondo números em fatores primos

Já que falamos sobre números primos nas últimas aulas, hoje vamos implementar uma função para decompor um dado número em fatores primos. Vamos relembrar como fazemos isso. 

Suponha que queremos decompor o número 30 em fatores primos.

• Dividimos 30 pelo menor número primo: 2. A divisão é exata, guardamos o número 2 e seguimos com o número 30/2 = 15.
• Dividimos 15 por 2. A divisão não é exata, então pegamos o próximo número primo.
• Dividimos 15 por 3. A divisão é exata, guardamos o número 3 e seguimos com o número 15/3 = 5.
• Dividimos 5 por 3. A divisão não é exata, então pegamos o próximo número primo.
• Dividimos 5 por 5. A divisão é exata, guardamos o número 5 e seguimos com o número 5/5 = 1.
• Como não há mais o que dividir (chegamos ao número 1), então o resultado é 2*3*5.

Desse modo, encontrar os fatores primos de um número significa dividir esse número sucessivamente pelo números primos em ordem crescente, guardando os que resultam em divisão exata. Note que, antes de passar para o próximo primo, testamos a divisão pelo primo atual novamente. Por exemplo, o número 8 é dividido por 2 três vezes, resultando em 2*2*2. 

Para implementarmos essa função, necessitamos de uma lista de números primos. Se você não tem uma lista guardada, pode criar uma e salvá-la em um arquivo para uso posterior. É o que faremos aqui, utilizando a função do crivo de Eratóstenes que construímos na última aula:

res = crivo_erat2(200)
saveRDS(res,"lista_primos.rds")

Desse modo, criamos uma lista de números primos e armazenamos na variável res. A segunda linha de código salva o que está armazenado em res em um arquivo chamado "lista_primos.rds". O arquivo será salvo no diretório atual do projeto. Caso queira especificar outro local, digite o caminho inteiro caso o destino esteja fora da pasta do projeto ou as subpastas caso esteja dentro da pasta do projeto.

Supostamente já temos uma lista de primos disponível e o passo acima apenas se refere a como salvar uma lista desse tipo. 

De fato, vamos começar nosso algoritmo carregando a lista de primos salva:

lista_primos = readRDS("lista_primos.rds")

> lista_primos
 [1]   2   3   5   7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71
[21]  73  79  83  89  97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173
[41] 179 181 191 193 197 199

Agora que temos a lista de números primos disponível, vamos implementar a função. Como dito, a decomposição em números primos se dá dividindo o número desejado sucessivamente pelos números primos da lista. O código é bem simples de entender:

fatora_em_primos = function(n,lista_p){
  resto = n;
  ind_p = 1;
  lista_f = NULL;
  while(resto>1){
    if(resto%%lista_p[ind_p]==0) {
      lista_f = c(lista_f,lista_p[ind_p]);
      resto = resto/lista_p[ind_p];
    }else{
      ind_p = ind_p +1;
    }
  }
  return(lista_f)
}

• A variável resto armazena o número escolhido e atualiza quando é dividido por um número primo.
• A variável ind_p armazena o índice atual da lista de primos.
• A variável lista_f armazena os fatores primos do número.
• A divisão é realizada até que resto seja igual a 1.

Vamos testar nossa função:

numero = 90;
result = fatora_em_primos(numero,lista_primos)

> result
[1] 2 3 3 5

Perceba que nossa função apresenta como resultado todos os fatores primos do número, podendo ser repetidos. No exemplo acima, 90 pode ser decomposto em 2*(3^2)*9. Como indicar quantas vezes o número 3 aparece e reduzir o vetor do resultado? Podemos utilizar a função table().

> table(result)
result
2 3 5 
1 2 1 

Agora sim obtemos uma lista de fatores primos únicos e quantas vezes cada um aparece. Matematicamente falando, os números da linha debaixo do resultado acima correspondem ao expoente do número primo correspondente da fatoração.

Se você não percebeu, há um problema na nossa função: e se a lista de números primos que é fornecida não é suficiente? Isso não é difícil de acontecer, basta pegarmos um número primo maior que o maior número primo da lista de primos. Por exemplo, o número 211 é primo e se executamos nossa função com a lista previamente carregada, obtemos:

> numero = 211;
> result = fatora_em_primos(numero,lista_primos)
Error in if (resto%%lista_p[ind_p] == 0) { : 
  missing value where TRUE/FALSE needed

O erro ocorre porque tentamos acessar um índice depois do fim do vetor de lista_p. Precisamos tratar esse erro.

Para isso, basta adicionar uma condição dentro do comando de repetição while, indicando que se o vetor lista_p foi totalmente percorrido e não obtemos o resultado, então devemos parar.

  while(resto>1){
    if(ind_p > length(lista_p)){
      cat("Lista de primos insuficiente!\n");
      return();
    }
    ...
  }

No código acima, além de pararmos a função e não retornarmos nada, printamos na tela uma mensagem para o usuário: "Lista de primos insuficiente!". Dessa forma, o usuário deve fornecer uma lista de números primos maior.

Se executamos nossa função com o número 211 novamente, obtemos:

> numero = 211;
> result = fatora_em_primos(numero,lista_primos)
Lista de primos insuficiente!

Pronto, agora temos uma função que decompõe um número escolhido em números primos e, caso não haja o fator na lista fornecida, outra lista é requerida.

Até a próxima aula!