Algoritmo de fator principal: C, Python Exemplo

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

O fator principal de um dado qualquer número é o fator que é um número primo. Os fatores quando multiplicados fornecem outro número. Um número primo é divisível por ele mesmo ou por 1.

Em outras palavras, os fatores primos são determinados descobrindo quais números primos se multiplicam para formar o número original.

Exemplo: Os fatores primos de 10 são 2 e 5. Isso ocorre porque 2X5 =10 e ambos 2,5 são números primos.

Encontrando os fatores principais usando iteração

Para encontrar os fatores primos de um determinado número, primeiro iteramos todos os números de 2 até a raiz quadrada do número e, em seguida, verificamos se cada número é primo. Contanto que o número original seja divisível por este primo, continuamos adicionando este primo a cada iteração.

Exemplo:

Todo número primo maior que 40 é escrito na seguinte fórmula: n²+n+41. Portanto, podemos substituir n por todos os números para encontrar o fator primo correspondente. por exemplo, 0²+0+41=41, 1²+1+41=43, 2²+2+41=47,…

Como imprimir um fator primo de um número?

• Neste método, iremos iterar os números de 2 até a raiz quadrada do número, conforme mencionado na seção anterior.
• Para isso, precisamos verificar o módulo do número original em cada um dos números de 2 até a raiz quadrada de n.
• Então, encontramos a lista de números primos que são fatores de n.
• Esta solução tem 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 Sieve depende do armazenamento do menor fator primo dos números, o que reduz visivelmente a complexidade ao calcular os fatores primos para qualquer número. O algoritmo Sieve encontra todos os fatores primos com certa eficiência.

• O conceito principal deste algoritmo é armazenar o menor fator primo de cada número até o número máximo.
• Pegamos o menor primo de cada número fornecido e o adicionamos ao conjunto de fatores primos.
• Por fim, dividimos por esse número primo e repetimos esses passos até chegar a 1.
• Tudo isso é feito em complexidade de tempo O(log(n)), melhorando muito a eficiência da solução.
• O que torna possível calcular os fatores primos de números muito maiores do que aqueles com os quais poderíamos ter lidado na abordagem anterior.

Exemplo:

A segunda maneira é verificar se o número pode ser escrito como 6n-1 ou 6n+1, pois qualquer número primo diferente de 2 e 3 deve ser escrito em uma das duas fórmulas. por exemplo, 5=6(1)-1, 19=6(3)+1,… .

Algoritmo:

Defina um array array para armazenar o menor fator primo de cada número com o valor do índice como um valor inicial para cada elemento do ordem.

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]

Python Fatores principais usando iteração

Aqui, mostraremos um código em Python linguagem para encontrar os fatores primos de um determinado número em um método iterativo:

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
4

Python Fatores principais usando recursão

Esta seção mostra um código em Python língua usando o método da peneira para encontrar os fatores primos de um determinado número.

import math
High = (int)(1e5+7)
array=[0 for i in range(High)]
# function to generate all the smallest prime 
def Sieve():
#factors of the numbers until the maximum  number
    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):
#We will keep dividing until we reach 1
    if n == 1:
        return
    print((int)(array[n]))
    PrimeFactors((int)(n/array[n]))
#Here we call the function after dividing it by this prime
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 que a python iterativa, mas escrita em Linguagem C.

Pedimos ao usuário que insira o número, então para cada número de 2 até a raiz quadrada desse número, precisamos verificar se ele é divisível imprimindo todas as ocorrências desse fator.

#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

Esta é a mesma solução que a recursiva python, mas escrita em C.

Podemos pedir ao usuário que insira o número; então, construímos o array de primos que armazena o menor fator primo de cada número. Por fim, chamamos de função recursiva Fatores Primos, que divide o número dado pelo seu menor fator primo e se recupera até chegar a um.

#include <stdio.h>
int Max = 100007;
int array[100007];
void Sieve()//helping function to generate all the smallest //prime factors of the numbers until the maximum number
{
    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)//keep dividing until we reach 1
    {
        return;
    }
    printf("%d\n",array[n]);
    PrimeFactors(n/array[n]);//call the function after dividing by //this prime
}
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

• Um dos fatos mais interessantes é que qualquer número par diferente de 2 pode ser a soma de dois números primos.
• Por exemplo: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3… etc.
• Outro fato é que não existem primos consecutivos além de 2 e 3, pois o único número primo par é o número 2.
• Além disso, todos os números primos, exceto 2 e 3, podem ser escritos na seguinte forma: 6 * n + 1 ou 6 * n – 1, onde n é um número inteiro positivo.
• O conjunto dos fatores primos de um número é único.
• O número 1 não é primo nem composto.
• A fatoração primária de números pode ajudar a resolver problemas como divisibilidade, simplificação de frações e localização de denominadores comuns de frações diferentes.
• Além disso, um dos usos interessantes da fatoração primária é quebrar códigos secretos baseados em números.