Algoritmo para encontrar o maior fator primo de um número
https://stackoverflow.com/questions/23287
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Qual é a melhor abordagem para calcular o maior fator primo de um número?
Estou pensando que o mais eficiente seria o seguinte:
- Encontre o menor número primo que se divide de forma limpa
- Verifique se o resultado da divisão é primo
- Se não, encontre o próximo valor mais baixo
- Vá para 2.
Estou baseando essa suposição no fato de ser mais fácil calcular os pequenos fatores primos.Isso está certo?Que outras abordagens devo considerar?
Editar:Agora percebi que minha abordagem é inútil se houver mais de dois fatores primos em jogo, pois a etapa 2 falha quando o resultado é um produto de dois outros primos, portanto, é necessário um algoritmo recursivo.
Edite novamente:E agora percebi que isso ainda funciona, porque o último número primo encontrado tem que ser o mais alto, portanto, qualquer teste adicional do resultado não primo da etapa 2 resultaria em um número primo menor.
Solução
Na verdade, existem várias maneiras mais eficientes de encontrar fatores de números grandes (para números menores, a divisão experimental funciona razoavelmente bem).
Um método que é muito rápido se o número de entrada tiver dois fatores muito próximos de sua raiz quadrada é conhecido como Fatoração de Fermat.Faz uso da identidade N = (a + b)(a - b) = a^2 - b^2 e é fácil de entender e implementar.Infelizmente não é muito rápido em geral.
O método mais conhecido para fatorar números de até 100 dígitos é o Peneira quadrática.Como bônus, parte do algoritmo é facilmente executada com processamento paralelo.
Ainda outro algoritmo do qual ouvi falar é Algoritmo Rho de Pollard.Não é tão eficiente quanto a Peneira Quadrática em geral, mas parece ser mais fácil de implementar.
Depois de decidir como dividir um número em dois fatores, aqui está o algoritmo mais rápido que consigo imaginar para encontrar o maior fator primo de um número:
Crie uma fila de prioridade que inicialmente armazene o próprio número.A cada iteração, você remove o número mais alto da fila e tenta dividi-lo em dois fatores (não permitindo que 1 seja um desses fatores, é claro).Se esta etapa falhar, o número é primo e você tem sua resposta!Caso contrário, você adiciona os dois fatores à fila e repete.
Outras dicas
Aqui está o melhor algoritmo que conheço (em Python)
def prime_factors(n):
"""Returns all the prime factors of a positive integer"""
factors = []
d = 2
while n > 1:
while n % d == 0:
factors.append(d)
n /= d
d = d + 1
return factors
pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list
O método acima é executado em O(n) no pior caso (quando a entrada é um número primo).
EDITAR:
Abaixo está o O(sqrt(n)) versão, conforme sugerido no comentário.Aqui está o código, mais uma vez.
def prime_factors(n):
"""Returns all the prime factors of a positive integer"""
factors = []
d = 2
while n > 1:
while n % d == 0:
factors.append(d)
n /= d
d = d + 1
if d*d > n:
if n > 1: factors.append(n)
break
return factors
pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list
Minha resposta é baseada em Tríptico's, mas melhora muito nisso.Baseia-se no fato de que além de 2 e 3, todos os números primos têm a forma 6n-1 ou 6n+1.
var largestPrimeFactor;
if(n mod 2 == 0)
{
largestPrimeFactor = 2;
n = n / 2 while(n mod 2 == 0);
}
if(n mod 3 == 0)
{
largestPrimeFactor = 3;
n = n / 3 while(n mod 3 == 0);
}
multOfSix = 6;
while(multOfSix - 1 <= n)
{
if(n mod (multOfSix - 1) == 0)
{
largestPrimeFactor = multOfSix - 1;
n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
}
if(n mod (multOfSix + 1) == 0)
{
largestPrimeFactor = multOfSix + 1;
n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
}
multOfSix += 6;
}
Recentemente escrevi um artigo do blog explicando como esse algoritmo funciona.
Eu arriscaria que um método no qual não há necessidade de um teste de primalidade (e nenhuma construção de peneira) funcionaria mais rápido do que aquele que os utiliza.Se for esse o caso, este é provavelmente o algoritmo mais rápido aqui.
Código JavaScript:
'option strict';
function largestPrimeFactor(val, divisor = 2) {
let square = (val) => Math.pow(val, 2);
while ((val % divisor) != 0 && square(divisor) <= val) {
divisor++;
}
return square(divisor) <= val
? largestPrimeFactor(val / divisor, divisor)
: val;
}
Exemplo de uso:
let result = largestPrimeFactor(600851475143);
Todos os números podem ser expressos como o produto de números primos, por exemplo:
102 = 2 x 3 x 17
712 = 2 x 2 x 2 x 89
Você pode encontrá-los simplesmente começando em 2 e continuando a dividir até que o resultado não seja um múltiplo do seu número:
712 / 2 = 356 .. 356 / 2 = 178 .. 178 / 2 = 89 .. 89 / 89 = 1
usando este método, você não precisa calcular nenhum número primo:todos serão primos, com base no fato de que você já fatorou o número tanto quanto possível com todos os números anteriores.
number = 712;
currNum = number; // the value we'll actually be working with
for (currFactor in 2 .. number) {
while (currNum % currFactor == 0) {
// keep on dividing by this number until we can divide no more!
currNum = currNum / currFactor // reduce the currNum
}
if (currNum == 1) return currFactor; // once it hits 1, we're done.
}
//this method skips unnecessary trial divisions and makes
//trial division more feasible for finding large primes
public static void main(String[] args)
{
long n= 1000000000039L; //this is a large prime number
long i = 2L;
int test = 0;
while (n > 1)
{
while (n % i == 0)
{
n /= i;
}
i++;
if(i*i > n && n > 1)
{
System.out.println(n); //prints n if it's prime
test = 1;
break;
}
}
if (test == 0)
System.out.println(i-1); //prints n if it's the largest prime factor
}
Semelhante à resposta do @Triptych, mas também diferente.Neste exemplo, lista ou dicionário não são usados.O código é escrito em Ruby
def largest_prime_factor(number)
i = 2
while number > 1
if number % i == 0
number /= i;
i -= 1
end
i += 1
end
return i
end
largest_prime_factor(600851475143)
# => 6857
A solução mais simples é um par de mutuamente recursivo funções.
A primeira função gera todos os números primos:
- Comece com uma lista de todos os números naturais maiores que 1.
- Remova todos os números que não são primos.Ou seja, números que não possuem fatores primos (além deles próprios).Veja abaixo.
A segunda função retorna os fatores primos de um determinado número n em ordem crescente.
- Faça uma lista de todos os primos (veja acima).
- Remova todos os números que não são fatores de
n.
O maior fator primo de n é o último número dado pela segunda função.
Este algoritmo requer um lista preguiçosa ou uma linguagem (ou estrutura de dados) com chamada por necessidade semântica.
Para esclarecimento, aqui está uma implementação (ineficiente) do acima em Haskell:
import Control.Monad
-- All the primes
primes = 2 : filter (ap (<=) (head . primeFactors)) [3,5..]
-- Gives the prime factors of its argument
primeFactors = factor primes
where factor [] n = []
factor xs@(p:ps) n =
if p*p > n then [n]
else let (d,r) = divMod n p in
if r == 0 then p : factor xs d
else factor ps n
-- Gives the largest prime factor of its argument
largestFactor = last . primeFactors
Tornar isso mais rápido é apenas uma questão de ser mais inteligente ao detectar quais números são primos e/ou fatores de n, mas o algoritmo permanece o mesmo.
n = abs(number);
result = 1;
if (n mod 2 == 0) {
result = 2;
while (n mod 2 = 0) n /= 2;
}
for(i=3; i<sqrt(n); i+=2) {
if (n mod i == 0) {
result = i;
while (n mod i = 0) n /= i;
}
}
return max(n,result)
Existem alguns testes de módulo que são supérfluos, pois n nunca poderá ser dividido por 6 se todos os fatores 2 e 3 tiverem sido removidos.Você só poderia permitir números primos para i, o que é mostrado em várias outras respostas aqui.
Na verdade, você poderia entrelaçar a peneira de Eratóstenes aqui:
- Primeiro, crie a lista de números inteiros até SQRT (N).
- Na marca FOR LOOP, todos os múltiplos de i até o novo SQRT (N) como não é o Prime e use um loop de tempo.
- Defina I para o próximo número primo da lista.
Veja também essa questão.
Estou ciente de que esta não é uma solução rápida.Postando como uma solução lenta, esperançosamente mais fácil de entender.
public static long largestPrimeFactor(long n) {
// largest composite factor must be smaller than sqrt
long sqrt = (long)Math.ceil(Math.sqrt((double)n));
long largest = -1;
for(long i = 2; i <= sqrt; i++) {
if(n % i == 0) {
long test = largestPrimeFactor(n/i);
if(test > largest) {
largest = test;
}
}
}
if(largest != -1) {
return largest;
}
// number is prime
return n;
}
Abordagem iterativa do Python, removendo todos os fatores primos do número
def primef(n):
if n <= 3:
return n
if n % 2 == 0:
return primef(n/2)
elif n % 3 ==0:
return primef(n/3)
else:
for i in range(5, int((n)**0.5) + 1, 6):
#print i
if n % i == 0:
return primef(n/i)
if n % (i + 2) == 0:
return primef(n/(i+2))
return n
Estou usando um algoritmo que continua dividindo o número pelo seu Fator Principal atual.
Minha solução em python 3:
def PrimeFactor(n):
m = n
while n%2==0:
n = n//2
if n == 1: # check if only 2 is largest Prime Factor
return 2
i = 3
sqrt = int(m**(0.5)) # loop till square root of number
last = 0 # to store last prime Factor i.e. Largest Prime Factor
while i <= sqrt :
while n%i == 0:
n = n//i # reduce the number by dividing it by it's Prime Factor
last = i
i+=2
if n> last: # the remaining number(n) is also Factor of number
return n
else:
return last
print(PrimeFactor(int(input())))
Entrada : 10Saída : 5
Entrada : 600851475143 Saída : 6857
Aqui está minha tentativa em c#.A última impressão é o maior fator primo do número.Eu verifiquei e funciona.
namespace Problem_Prime
{
class Program
{
static void Main(string[] args)
{
/*
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
*/
long x = 600851475143;
long y = 2;
while (y < x)
{
if (x % y == 0)
{
// y is a factor of x, but is it prime
if (IsPrime(y))
{
Console.WriteLine(y);
}
x /= y;
}
y++;
}
Console.WriteLine(y);
Console.ReadLine();
}
static bool IsPrime(long number)
{
//check for evenness
if (number % 2 == 0)
{
if (number == 2)
{
return true;
}
return false;
}
//don't need to check past the square root
long max = (long)Math.Sqrt(number);
for (int i = 3; i <= max; i += 2)
{
if ((number % i) == 0)
{
return false;
}
}
return true;
}
}
}
#python implementation
import math
n = 600851475143
i = 2
factors=set([])
while i<math.sqrt(n):
while n%i==0:
n=n/i
factors.add(i)
i+=1
factors.add(n)
largest=max(factors)
print factors
print largest
Calcula o maior fator primo de um número usando recursão em C++.O funcionamento do código é explicado abaixo:
int getLargestPrime(int number) {
int factor = number; // assumes that the largest prime factor is the number itself
for (int i = 2; (i*i) <= number; i++) { // iterates to the square root of the number till it finds the first(smallest) factor
if (number % i == 0) { // checks if the current number(i) is a factor
factor = max(i, number / i); // stores the larger number among the factors
break; // breaks the loop on when a factor is found
}
}
if (factor == number) // base case of recursion
return number;
return getLargestPrime(factor); // recursively calls itself
}
Aqui está minha abordagem para calcular rapidamente o maior fator primo.Baseia-se no fato de que modificado x não contém fatores não primos.Para conseguir isso, dividimos x assim que um fator for encontrado.Então, a única coisa que resta é retornar o maior fator.Já seria primo.
O código (Haskell):
f max' x i | i > x = max'
| x `rem` i == 0 = f i (x `div` i) i -- Divide x by its factor
| otherwise = f max' x (i + 1) -- Check for the next possible factor
g x = f 2 x 2
O algoritmo C++ a seguir não é o melhor, mas funciona para números abaixo de um bilhão e é bastante rápido
#include <iostream>
using namespace std;
// ------ is_prime ------
// Determines if the integer accepted is prime or not
bool is_prime(int n){
int i,count=0;
if(n==1 || n==2)
return true;
if(n%2==0)
return false;
for(i=1;i<=n;i++){
if(n%i==0)
count++;
}
if(count==2)
return true;
else
return false;
}
// ------ nextPrime -------
// Finds and returns the next prime number
int nextPrime(int prime){
bool a = false;
while (a == false){
prime++;
if (is_prime(prime))
a = true;
}
return prime;
}
// ----- M A I N ------
int main(){
int value = 13195;
int prime = 2;
bool done = false;
while (done == false){
if (value%prime == 0){
value = value/prime;
if (is_prime(value)){
done = true;
}
} else {
prime = nextPrime(prime);
}
}
cout << "Largest prime factor: " << value << endl;
}
Encontrei esta solução na web por "James Wang"
public static int getLargestPrime( int number) {
if (number <= 1) return -1;
for (int i = number - 1; i > 1; i--) {
if (number % i == 0) {
number = i;
}
}
return number;
}
Fator principal usando peneira:
#include <bits/stdc++.h>
using namespace std;
#define N 10001
typedef long long ll;
bool visit[N];
vector<int> prime;
void sieve()
{
memset( visit , 0 , sizeof(visit));
for( int i=2;i<N;i++ )
{
if( visit[i] == 0)
{
prime.push_back(i);
for( int j=i*2; j<N; j=j+i )
{
visit[j] = 1;
}
}
}
}
void sol(long long n, vector<int>&prime)
{
ll ans = n;
for(int i=0; i<prime.size() || prime[i]>n; i++)
{
while(n%prime[i]==0)
{
n=n/prime[i];
ans = prime[i];
}
}
ans = max(ans, n);
cout<<ans<<endl;
}
int main()
{
ll tc, n;
sieve();
cin>>n;
sol(n, prime);
return 0;
}
Parece-me que a etapa 2 do algoritmo fornecido não será uma abordagem tão eficiente.Você não tem nenhuma expectativa razoável de que seja primo.
Além disso, a resposta anterior sugerindo a Peneira de Eratóstenes está totalmente errada.Acabei de escrever dois programas para fatorar 123456789.Um foi baseado no Sieve, o outro foi baseado no seguinte:
1) Test = 2
2) Current = Number to test
3) If Current Mod Test = 0 then
3a) Current = Current Div Test
3b) Largest = Test
3c) Goto 3.
4) Inc(Test)
5) If Current < Test goto 4
6) Return Largest
Esta versão foi 90x mais rápida que o Sieve.
Acontece que nos processadores modernos o tipo de operação importa muito menos do que o número de operações, sem falar que o algoritmo acima pode rodar em cache, o Sieve não.A peneira usa muitas operações eliminando todos os números compostos.
Observe, também, que minha divisão dos fatores à medida que são identificados reduz o espaço que deve ser testado.
Calcule primeiro uma lista armazenando números primos, por ex.2 3 5 7 11 13 ...
Cada vez que você fatora um número como primo, use a implementação do Triptych, mas iterando essa lista de números primos em vez de números inteiros naturais.
Com Java:
Para int valores:
public static int[] primeFactors(int value) {
int[] a = new int[31];
int i = 0, j;
int num = value;
while (num % 2 == 0) {
a[i++] = 2;
num /= 2;
}
j = 3;
while (j <= Math.sqrt(num) + 1) {
if (num % j == 0) {
a[i++] = j;
num /= j;
} else {
j += 2;
}
}
if (num > 1) {
a[i++] = num;
}
int[] b = Arrays.copyOf(a, i);
return b;
}
Para long valores:
static long[] getFactors(long value) {
long[] a = new long[63];
int i = 0;
long num = value;
while (num % 2 == 0) {
a[i++] = 2;
num /= 2;
}
long j = 3;
while (j <= Math.sqrt(num) + 1) {
if (num % j == 0) {
a[i++] = j;
num /= j;
} else {
j += 2;
}
}
if (num > 1) {
a[i++] = num;
}
long[] b = Arrays.copyOf(a, i);
return b;
}
Provavelmente isso nem sempre é mais rápido, mas é mais otimista quanto ao fato de você encontrar um grande divisor principal:
Né o seu número- Se for primo então
return(N) - Calcule os números primos até
Sqrt(N) - Percorra os números primos em ordem decrescente (o maior primeiro)
- Se
N is divisible by PrimeentãoReturn(Prime)
- Se
Editar:No passo 3 você pode usar a peneira de Eratóstenes ou a peneira de Atkins ou o que quiser, mas por si só a peneira não encontrará o maior fator primo.(É por isso que eu não escolheria a postagem do SQLMenace como resposta oficial ...)
Acho que seria bom armazenar em algum lugar todos os primos possíveis menores que n e apenas iterá-los para encontrar o maior divisor.Você pode obter números primos de números primos.org.
Claro que presumo que o seu número não seja muito grande :)
Não é o mais rápido, mas funciona!
static bool IsPrime(long num)
{
long checkUpTo = (long)Math.Ceiling(Math.Sqrt(num));
for (long i = 2; i <= checkUpTo; i++)
{
if (num % i == 0)
return false;
}
return true;
}
Aqui está a mesma função@Triptych fornecida como gerador, que também foi ligeiramente simplificada.
def primes(n):
d = 2
while (n > 1):
while (n%d==0):
yield d
n /= d
d += 1
o máximo primo pode então ser encontrado usando:
n= 373764623
max(primes(n))
e uma lista de fatores encontrados usando:
list(primes(n))
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include <time.h>
factor(long int n)
{
long int i,j;
while(n>=4)
{
if(n%2==0) { n=n/2; i=2; }
else
{ i=3;
j=0;
while(j==0)
{
if(n%i==0)
{j=1;
n=n/i;
}
i=i+2;
}
i-=2;
}
}
return i;
}
void main()
{
clock_t start = clock();
long int n,sp;
clrscr();
printf("enter value of n");
scanf("%ld",&n);
sp=factor(n);
printf("largest prime factor is %ld",sp);
printf("Time elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);
getch();
}
