Algoritmo per trovare il fattore primo più grande di un numero
https://stackoverflow.com/questions/23287
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Qual è l'approccio migliore per calcolare il più grande fattore primo di un numero?
Penso che il più efficiente sarebbe il seguente:
- Trova il numero primo più basso che divide in modo netto
- Controlla se il risultato della divisione è primo
- In caso contrario, trova il successivo più basso
- Vai a 2.
Baso questa ipotesi sul fatto che sarebbe più semplice calcolare i piccoli fattori primi.E' giusto?Quali altri approcci dovrei esaminare?
Modificare:Ora mi sono reso conto che il mio approccio è inutile se ci sono più di 2 fattori primi in gioco, poiché il passaggio 2 fallisce quando il risultato è un prodotto di altri due fattori primi, quindi è necessario un algoritmo ricorsivo.
Modifica di nuovo:E ora ho capito che funziona ancora, perché l'ultimo numero primo trovato deve essere il più alto, quindi qualsiasi ulteriore test del risultato non primo del passaggio 2 risulterebbe in un numero primo più piccolo.
Soluzione
In realtà ci sono molti modi più efficienti per trovare i fattori di grandi numeri (per quelli più piccoli la divisione di prova funziona abbastanza bene).
Un metodo che è molto veloce se il numero immesso ha due fattori molto vicini alla sua radice quadrata è noto come Fattorizzazione di Fermat.Fa uso dell'identità N = (a + b)(a - b) = a^2 - b^2 ed è facile da capire e implementare.Sfortunatamente non è molto veloce in generale.
Il metodo più conosciuto per fattorizzare numeri lunghi fino a 100 cifre è il Setaccio quadratico.Come bonus, parte dell'algoritmo può essere eseguita facilmente con l'elaborazione parallela.
Ancora un altro algoritmo di cui ho sentito parlare è Algoritmo Rho di Pollard.Non è efficiente quanto il Setaccio Quadratico in generale, ma sembra essere più facile da implementare.
Una volta deciso come dividere un numero in due fattori, ecco l'algoritmo più veloce che mi viene in mente per trovare il fattore primo più grande di un numero:
Crea una coda prioritaria che inizialmente memorizza il numero stesso.Ad ogni iterazione, rimuovi il numero più alto dalla coda e tenti di dividerlo in due fattori (non consentendo che 1 sia uno di questi fattori, ovviamente).Se questo passaggio fallisce, il numero è primo e hai la tua risposta!Altrimenti aggiungi i due fattori alla coda e ripeti.
Altri suggerimenti
Ecco il miglior algoritmo che conosco (in 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
Il metodo sopra viene eseguito O(n) nel caso peggiore (quando l'input è un numero primo).
MODIFICARE:
Di seguito è riportato il O(sqrt(n)) versione, come suggerito nel commento.Ecco il codice, ancora una volta.
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
La mia risposta è basata su Trittico's, ma migliora molto.Si basa sul fatto che oltre il 2 e il 3 tutti i numeri primi sono della forma 6n-1 o 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 ho scritto a articolo del blog spiegando come funziona questo algoritmo.
Oserei dire che un metodo in cui non è necessario un test per la primalità (e nessuna costruzione di setacci) funzionerebbe più velocemente di uno che li utilizza.Se è così, questo è probabilmente l'algoritmo più veloce qui.
Codice 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;
}
Esempio di utilizzo:
let result = largestPrimeFactor(600851475143);
Tutti i numeri possono essere espressi come prodotto di numeri primi, ad esempio:
102 = 2 x 3 x 17
712 = 2 x 2 x 2 x 89
Puoi trovarli semplicemente iniziando da 2 e continuando a dividere finché il risultato non è un multiplo del tuo numero:
712 / 2 = 356 .. 356 / 2 = 178 .. 178 / 2 = 89 .. 89 / 89 = 1
usando questo metodo non devi effettivamente calcolare alcun numero primo:saranno tutti primi, in base al fatto che hai già fattorizzato il numero il più possibile con tutti i numeri precedenti.
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
}
Simile alla risposta @Triptych ma anche diversa.In questo esempio non viene utilizzato l'elenco o il dizionario.Il codice è scritto in 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
La soluzione più semplice è una coppia di reciprocamente ricorsivi funzioni.
La prima funzione genera tutti i numeri primi:
- Inizia con un elenco di tutti i numeri naturali maggiori di 1.
- Rimuovi tutti i numeri che non sono primi.Cioè, numeri che non hanno fattori primi (oltre a loro stessi).Vedi sotto.
La seconda funzione restituisce i fattori primi di un dato numero n in ordine crescente.
- Prendi un elenco di tutti i numeri primi (vedi sopra).
- Rimuovi tutti i numeri che non sono fattori di
n.
Il più grande fattore primo di n è l'ultimo numero dato dalla seconda funzione.
Questo algoritmo richiede a Lista pigra o un linguaggio (o struttura dati) con chiamata per necessità semantica.
Per chiarimenti, ecco un'implementazione (inefficiente) di quanto sopra in 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
Renderlo più veloce è solo questione di essere più intelligenti nel rilevare quali numeri sono primi e/o fattori di n, ma l'algoritmo rimane lo stesso.
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)
Ci sono alcuni test modulo che sono superflui, poiché n non può mai essere diviso per 6 se tutti i fattori 2 e 3 sono stati rimossi.Potresti consentire solo numeri primi per i, che è mostrato in molte altre risposte qui.
Potresti effettivamente intrecciare il setaccio di Eratostene qui:
- Crea innanzitutto l'elenco dei numeri interi fino a SQRT (N).
- Nel segnale per loop tutti i multipli di I fino al nuovo SQRT (N) come non Prime, e usa invece un ciclo while.
- Imposta I sul numero Prime successivo nell'elenco.
Vedi anche questa domanda.
Sono consapevole che questa non è una soluzione rapida.Pubblicazione come soluzione lenta, si spera, più facile da comprendere.
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;
}
Approccio iterativo Python rimuovendo tutti i fattori primi dal numero
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
Sto utilizzando un algoritmo che continua a dividere il numero per il suo attuale fattore primo.
La mia soluzione in 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())))
Ingresso: 10Produzione : 5
Ingresso: 600851475143 Produzione : 6857
Ecco il mio tentativo in C#.L'ultima stampa è il fattore primo più grande del numero.Ho controllato e funziona.
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
Calcola il fattore primo più grande di un numero utilizzando la ricorsione in C++.Il funzionamento del codice è spiegato di seguito:
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
}
Ecco il mio approccio per calcolare rapidamente il fattore primo più grande.Si basa sul fatto che è stato modificato x non contiene fattori non primi.Per raggiungere questo obiettivo, dividiamo x non appena viene trovato un fattore.Quindi, l'unica cosa rimasta è restituire il fattore più grande.Sarebbe già primo.
Il codice (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
Il seguente algoritmo C++ non è il migliore, ma funziona per numeri inferiori al miliardo ed è piuttosto veloce
#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;
}
Ho trovato questa soluzione sul web da "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;
}
Fattore primo utilizzando il setaccio:
#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;
}
Mi sembra che il passaggio n. 2 dell'algoritmo fornito non sarà un approccio così efficiente.Non hai alcuna ragionevole aspettativa che sia primo.
Inoltre, la risposta precedente che suggerisce il Setaccio di Eratostene è completamente sbagliata.Ho appena scritto due programmi per fattorizzare 123456789.Uno era basato sul Setaccio, l'altro era basato su quanto segue:
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
Questa versione era 90 volte più veloce del Sieve.
Il fatto è che sui processori moderni il tipo di operazione conta molto meno del numero di operazioni, per non parlare del fatto che l'algoritmo di cui sopra può essere eseguito nella cache, il Sieve no.Il Setaccio utilizza molte operazioni cancellando tutti i numeri compositi.
Si noti, inoltre, che la mia suddivisione dei fattori man mano che vengono identificati riduce lo spazio che deve essere testato.
Calcola prima una lista che memorizza i numeri primi, ad es.2 3 5 7 11 13 ...
Ogni volta che scomponi in fattori primi un numero, utilizza l'implementazione di Triptych ma ripetendo questo elenco di numeri primi anziché di interi naturali.
Con Java:
Per int valori:
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;
}
Per long valori:
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;
}
Questo probabilmente non è sempre più veloce ma più ottimista riguardo al fatto che trovi un grande divisore primo:
Nè il tuo numero- Se è primo allora
return(N) - Calcola i numeri primi fino a
Sqrt(N) - Scorri i numeri primi in ordine decrescente (prima il più grande)
- Se
N is divisible by PrimePoiReturn(Prime)
- Se
Modificare:Nel passaggio 3 puoi usare il Setaccio di Eratostene o il Setaccio di Atkins o quello che preferisci, ma da solo il setaccio non ti troverà il fattore primo più grande.(Ecco perché non sceglierei il post di SQLMenace come risposta ufficiale...)
Penso che sarebbe bene memorizzare da qualche parte tutti i possibili numeri primi più piccoli di n e scorrerli semplicemente per trovare il divisore più grande.Puoi ottenere i numeri primi da prime-numbers.org.
Ovviamente presumo che il tuo numero non sia troppo grande :)
Non è il più veloce ma funziona!
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;
}
Ecco la stessa funzione@Triptych fornita come generatore, anch'essa leggermente semplificata.
def primes(n):
d = 2
while (n > 1):
while (n%d==0):
yield d
n /= d
d += 1
il numero primo massimo può quindi essere trovato utilizzando:
n= 373764623
max(primes(n))
e un elenco di fattori rilevati utilizzando:
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();
}
