C# - Calculando os fatores primos de um número

Na teoria dos números, os fatores primos de um inteiro positivo são os números primos que dividem esse inteiro exatamente.

A fatoração de um número inteiro positivo é uma lista de fatores primos do número inteiro, juntamente com suas multiplicidades, o processo de determinar esses fatores também podem ser referidos como "fatoração".

Teoria

Fatoração (português brasileiro) ou Fatorização (português europeu) (AO 1945: Factorização) é o termo usado na álgebra para designar a decomposição que se faz de cada um dos elementos que integram um produto, ou seja, o resultado de uma multiplicação.

Assim como parcela é cada uma das partes que integram uma adição, o fator é como se chama cada elemento que integra o produto.

Com a fatoração busca-se a simplificação das fórmulas matemáticas em que ocorre a multiplicação, especialmente das chamadas equações.(Wikipédia)

Assim , fatorar um número, é expressá-lo no formato de uma multiplicação de fatores. Vamos a alguns exemplos:

b) O número 18 pode ser escrito como uma multiplicação de fatores das seguintes formas:

18 = 2 x 9
18 = 3 x 6
18 = 1 x 18

Para descobrir os fatores de um número natural, vamos considerar o número 40. 
40 x 1 = 40
4 x 10 = 40
5 x 8 = 40
20 x 2 = 40

Sendo assim, os números 1, 2 , 4, 5, 8, 10, 20 e 40 são fatores do número natural 40. 

Agora vamos descobrir todos os números naturais que se dividem exatamente (sem resto) pelo número 40: 

40 : 1 = 40
40 : 40 = 1
40 : 2 = 20
40 : 20 = 2
40 : 4 = 10
40 : 10 = 4
40 : 5 = 8
40 : 8 = 5 

Então, os divisores de 40 são: 1, 2, 4, 5, 8, 10, 20, 40. 

Observe que os fatores e os divisores do número natural 40 são os mesmos. As ideias de fatores e divisores de um mesmo número natural, estão ligadas. 

Isso quer dizer que podemos encontrar os divisores de um número natural, descobrindo os seus fatores. 

Assim os fatores primos para o número 9360  são: 13 *  5 *  3 *  3 *  2 *  2 *  2 *  2

Observe que os números 13, 5, 3, 2 são números primos.

Para um fator primo p de n, a multiplicidade de p é o maior expoente x para o qual p^x (p elevado a x) divide n exatamente.

Para um inteiro positivo n, o número de fatores primos de n e a soma dos fatores primos de n (não contando multiplicidade) são exemplos de funções aritméticas de n que são aditivas, mas não completamente aditivas.

Vamos então criar um projeto usando a linguagem C# para calcular os fatores primos de um número.

Criando o projeto

Os recursos usados para criar o projeto são:

Abra o VS 2012 Express for desktop e clique em New Project;

Selecione a Visual C# -> Windows e o template Windows Forms Application informando o nome FatoresPrimos e clicando em OK;

No formulário padrão form1.cs inclua os seguintes controles a partir da ToolBox:

Define o seguinte leiaute para este formulário:

No menu PROJECT clique em Add Class  e informe o nome Calculo.cs para este arquivo:

A seguir vamos definir dois métodos estáticos na classe Calculo:

  1. IsNumeroPrimo  - retorna True se um número for primo e False se não for;
  2. GetFatoresPrimos -  retorna um array com os fatores primos de um número;
namespace FatoresPrimos
{
    public static class Calculo
    {
        const int MAX_SIZE = 15000;

        static bool IsNumeroPrimo(int numero)
        {
            bool bPrimo = true;
            int fator = numero / 2;
            int i = 0;
            for (i = 2; i <= fator; i++)
            {
                if ((numero % i) == 0)
                    bPrimo = false;
           }
            return bPrimo;
       }
        static public int GetFatoresPrimos(int numero, out int[] arrResultado)
        {
            int contador = 0;
            int[] vetor = new int[MAX_SIZE];
            arrResultado = new int[MAX_SIZE];
            int i = 0;
            int indice = 0;
            for (i = 2; i <= numero; i++)
            {
                if (IsNumeroPrimo(i) == true)
                    vetor[contador++] = i;
            }
            while (true)
            {
                if (IsNumeroPrimo(numero) == true)
                {
                    arrResultado[indice++] = numero;
                    break;
                }
                for (i = contador - 1; i >= 0; i--)
                {
                    if ((numero % vetor[i]) == 0)
                    {
                        arrResultado[indice++] = vetor[i];
                        numero = numero / vetor[i];
                        break;
                    }
               }
            }
            return indice;
        }
    }
}

Tudo pronto ! Vamos definir o código no evento Click do botão de comando Calcular conforme abaixo:

 private void btnCalcular_Click(object sender, EventArgs e)
        {
            lbFatores.Items.Clear();
            int numero = Convert.ToInt32(txtValor.Text);
            int contador = Calculo.GetFatoresPrimos(numero, out arrResultado);
            for (int i = 0; i < contador; i++)
            {
                lbFatores.Items.Add(arrResultado[i]);
                if (i != contador - 1)
                    lbFatores.Items.Add("*");
                    lbFatores.Items.Add(string.Format("{0} {1}", arrResultado[i], "*"));
            }
        }

 

Vemos abaixo o resultado da execução do projeto:

Pegue o projeto completo aqui: FatoresPrimos.zip

Joã 8:45 Mas porque eu digo a verdade, não me credes.

Joã 8:46 Quem dentre vós me convence de pecado? Se digo a verdade, por que não me credes?

Joã 8:47 Quem é de Deus ouve as palavras de Deus; por isso vós não as ouvis, porque não sois de Deus.

Referências:

José Carlos Macoratti