Algoritmo de fator principal: C, Python Exemplo

O que é uma fatoração primária?

O fator primo de um número é um fator que também é um número. número primo, divisível apenas por 1 e por si mesmo.

Exemplo: Os fatores primos de 10 são 2 e 5, pois 2 × 5 = 10.

Encontrando os fatores principais usando iteração

Itere de 2 até sqrt(n) e verifique a divisibilidade. Enquanto n for divisível pelo candidato atual, divida e imprima.

Exemplo: todo número primo maior que 40 se encaixa n²+n+41, então n = 0, 1, 2 resulta em 41, 43, 47.

Como imprimir um fator primo de um número?

• Itere os números de 2 até sqrt(n).
• Verifique o módulo de n em relação a cada candidato; um resto zero significa que o candidato é um fator primo.
• Colete todos os números primos que dividem n.
• A rotina é executada em complexidade de tempo O(sqrt(n)).

Algoritmo:

Set a counter i to 2
While i <= sqrt(n):
    While n % i == 0:
        n = n / i
        print i
    i = i + 1
if n > 1:
    print n

Algoritmo de peneira

O método do Crivo armazena o menor fator primo de cada número até um limite máximo, reduzindo drasticamente o custo da fatoração após o pré-cálculo.

• Registre o menor fator primo de cada número inteiro até o limite máximo.
• Pegue o menor número de primos e adicione-o ao conjunto de fatores.
• Divida o número por esse número primo e repita até que o resultado seja 1.
• Cada consulta é executada em aproximadamente O(log n).

Exemplo: um primo diferente de 2 e 3 se encaixa na forma 6n-1 ou 6n+1. Por exemplo, 5 = 6(1)-1 e 19 = 6(3)+1.

Algoritmo: definir um ordem que armazena o menor fator primo de cada número, usando o índice como valor inicial para cada elemento.

Set array[1] to 1
Set i to 2
While i*i <= max_number:
    If array[i] == i:
        Set j to i*i
        While j <= max_number:
            If array[j] == j:
                array[j] = i
            j = j + i
    i = i + 1
while the_number != 1:
    print array[the_number]
    the_number = the_number / array[the_number]

Artigos Relacionados

• Estrutura de dados do gráfico e Algorithms
• Problema do Vendedor Viajante
• Algoritmo do Método da Bissecção
• Algoritmo de classificação de intervalo

Python Fatores principais usando iteração

Os seguintes Python O código encontra os fatores primos usando o método iterativo de divisão por tentativa:

import math
def PrimeFactors(n):
    for i in range(2, int(math.sqrt(n)) + 1, 1):
        while n % i == 0:  # find all the occurrences of a prime factor
            print((int)(i))
            n = n // i
    if n != 1:  # if the number was originally a prime
        print((int)(n))
n = (int)(input("Enter the number you want: "))
PrimeFactors(n)

Saída:

Enter the number you want: 4
2
2

Python Fatores principais usando recursão

O Python O código abaixo utiliza o método do crivo para encontrar os fatores primos de um número dado.

import math
High = (int)(1e5 + 7)
array = [0 for i in range(High)]

# generate smallest prime factors
def Sieve():
    for i in range(1, High):
        array[i] = i
    for i in range(2, math.ceil(math.sqrt(High))):
        if array[i] == i:
            for j in range(i * i, High, i):
                if array[j] == j:
                    array[j] = i

def PrimeFactors(n):  # divide until we reach 1
    if n == 1:
        return
    print((int)(array[n]))
    PrimeFactors((int)(n / array[n]))

Sieve()
n = (int)(input("Enter the number you want: "))
PrimeFactors(n)

Saída:

Enter the number you want: 4
2
2

Programa de fatores primos C usando iteração

A mesma solução iterativa escrita em CInsira um número e, para cada candidato de 2 até sqrt(n), verifique a divisibilidade e imprima todas as ocorrências de um fator primo.

#include <stdio.h>
int main()
{
    int n;
    printf("Enter the number you want: ");
    scanf("%d", &n);
    for (int i = 2; i * i <= n; i++)
    {
        while (n % i == 0)  // find all the occurrences of a prime factor
        {
            printf("%d\n", i);
            n /= i;
        }
    }
    if (n != 1)  // if the number was originally a prime
    {
        printf("%d", n);
    }
    return 0;
}

Saída:

Enter the number you want: 2
2

Programa C Prime Factors usando recursão

A versão recursiva em C espelha a Python Uma das opções é construir a matriz dos menores fatores primos e, em seguida, repetir a divisão por esse fator até que n chegue a 1.

#include <stdio.h>
int Max = 100007;
int array[100007];

void Sieve()  // smallest prime factors up to Max
{
    for (int i = 1; i < Max; i++)
        array[i] = i;
    for (int i = 2; i * i <= Max; i++)
    {
        if (array[i] == i)
        {
            for (int j = i * i; j < Max; j += i)
            {
                if (array[j] == j)
                    array[j] = i;
            }
        }
    }
}

void PrimeFactors(int n)
{
    if (n == 1)  // divide until we reach 1
        return;
    printf("%d\n", array[n]);
    PrimeFactors(n / array[n]);
}

int main()
{
    Sieve();
    int n;
    printf("Enter the number you want: ");
    scanf("%d", &n);
    PrimeFactors(n);
    return 0;
}

Saída:

Enter the number you want: 2
2

Alguns fatos interessantes sobre números primos

• Qualquer número par diferente de 2 pode ser escrito como a soma de dois números primos (4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3).
• Não existem outros números primos consecutivos além de 2 e 3, pois 2 é o único número primo par.
• Todos os números primos, exceto 2 e 3, têm a forma 6n + 1 ou 6n − 1, onde n é um número inteiro positivo.
• O conjunto de fatores primos de um número é único.
• O número 1 não é primo nem composto.
• A fatoração em números primos auxilia na divisibilidade, simplificação de frações e na identificação de denominadores comuns.
• A fatoração em números primos também é fundamental para códigos criptográficos baseados em números.

Perguntas Frequentes