Algorithme pour trouver le plus grand facteur premier d'un nombre
https://stackoverflow.com/questions/23287
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Quelle est la meilleure approche pour calculer le plus grand facteur premier d’un nombre ?
Je pense que le plus efficace serait le suivant :
- Trouver le nombre premier le plus bas qui se divise proprement
- Vérifiez si le résultat de la division est premier
- Sinon, trouvez le prochain plus bas
- Allez à 2.
Je base cette hypothèse sur le fait qu'il est plus facile de calculer les petits facteurs premiers.Est-ce à peu près vrai ?Quelles autres approches devrais-je envisager ?
Modifier:J'ai maintenant réalisé que mon approche est futile s'il y a plus de 2 facteurs premiers en jeu, puisque l'étape 2 échoue lorsque le résultat est un produit de deux autres facteurs premiers, donc un algorithme récursif est nécessaire.
Modifier à nouveau :Et maintenant, j'ai réalisé que cela fonctionne toujours, car le dernier nombre premier trouvé doit être le plus élevé, donc tout test supplémentaire du résultat non premier de l'étape 2 entraînerait un nombre premier plus petit.
La solution
En fait, il existe plusieurs façons plus efficaces de trouver des facteurs de grands nombres (pour les plus petits, la division d'essai fonctionne raisonnablement bien).
Une méthode très rapide si le nombre saisi a deux facteurs très proches de sa racine carrée est connue sous le nom de Factorisation de Fermat.Il utilise l'identité N = (a + b)(a - b) = a^2 - b^2 et est facile à comprendre et à mettre en œuvre.Malheureusement, ce n'est pas très rapide en général.
La méthode la plus connue pour factoriser des nombres comportant jusqu'à 100 chiffres est la Tamis quadratique.En prime, une partie de l’algorithme se réalise facilement avec un traitement parallèle.
Un autre algorithme dont j'ai entendu parler est Algorithme Rho de Pollard.Ce n'est pas aussi efficace que le Quadratic Sieve en général mais semble plus facile à mettre en œuvre.
Une fois que vous avez décidé comment diviser un nombre en deux facteurs, voici l'algorithme le plus rapide auquel je puisse penser pour trouver le plus grand facteur premier d'un nombre :
Créez une file d'attente prioritaire qui stocke initialement le numéro lui-même.À chaque itération, vous supprimez le nombre le plus élevé de la file d'attente et essayez de le diviser en deux facteurs (en ne permettant pas à 1 d'être l'un de ces facteurs, bien sûr).Si cette étape échoue, le nombre est premier et vous avez votre réponse !Sinon, vous ajoutez les deux facteurs dans la file d'attente et répétez.
Autres conseils
Voici le meilleur algorithme que je connaisse (en 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
La méthode ci-dessus s'exécute dans O(n) dans le pire des cas (lorsque l'entrée est un nombre premier).
MODIFIER:
Ci-dessous se trouve le O(sqrt(n)) version, comme suggéré dans le commentaire.Voici à nouveau le code.
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
Ma réponse est basée sur Triptyque's, mais l'améliore beaucoup.Elle repose sur le fait qu'au-delà de 2 et 3, tous les nombres premiers sont de la forme 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;
}
J'ai récemment écrit un article de blog expliquant comment fonctionne cet algorithme.
J'oserais dire qu'une méthode dans laquelle il n'y a pas besoin de test de primalité (et pas de construction de tamis) fonctionnerait plus rapidement qu'une méthode qui les utilise.Si tel est le cas, il s’agit probablement de l’algorithme le plus rapide.
Code 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;
}
Exemple d'utilisation :
let result = largestPrimeFactor(600851475143);
Tous les nombres peuvent être exprimés comme le produit de nombres premiers, par exemple :
102 = 2 x 3 x 17
712 = 2 x 2 x 2 x 89
Vous pouvez les trouver en commençant simplement par 2 et en continuant simplement à diviser jusqu'à ce que le résultat ne soit pas un multiple de votre nombre :
712 / 2 = 356 .. 356 / 2 = 178 .. 178 / 2 = 89 .. 89 / 89 = 1
en utilisant cette méthode, vous n'avez pas besoin de calculer de nombres premiers :ils seront tous premiers, sur la base du fait que vous avez déjà factorisé le nombre autant que possible avec tous les nombres précédents.
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
}
Semblable à la réponse @Triptych mais aussi différente.Dans cet exemple, la liste ou le dictionnaire n'est pas utilisé.Le code est écrit en 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 solution la plus simple est une paire de mutuellement récursif les fonctions.
La première fonction génère tous les nombres premiers :
- Commencez par une liste de tous les nombres naturels supérieurs à 1.
- Supprimez tous les nombres qui ne sont pas premiers.C'est-à-dire des nombres qui n'ont pas de facteurs premiers (autres qu'eux-mêmes).Voir ci-dessous.
La deuxième fonction renvoie les facteurs premiers d'un nombre donné n par ordre croissant.
- Faites une liste de tous les nombres premiers (voir ci-dessus).
- Supprimez tous les nombres qui ne sont pas des facteurs de
n.
Le plus grand facteur premier de n est le dernier nombre donné par la deuxième fonction.
Cet algorithme nécessite un Liste paresseux ou un langage (ou une structure de données) avec appel par besoin sémantique.
Pour plus de clarté, voici une implémentation (inefficace) de ce qui précède dans 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
Pour rendre cela plus rapide, il suffit d'être plus intelligent dans la détection des nombres premiers et/ou des facteurs de n, mais l'algorithme reste le même.
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)
Certains tests modulo sont superflus, car n ne peut jamais être divisé par 6 si tous les facteurs 2 et 3 ont été supprimés.Vous ne pouvez autoriser que les nombres premiers pour i, ce qui est indiqué dans plusieurs autres réponses ici.
Vous pourriez en fait entrelacer le tamis d’Ératosthène ici :
- D'abord créer la liste des entiers vers le haut à sqrt(n).
- Dans la boucle for marquer tous les multiples de i jusqu'au nouveau sqrt(n) comme non prime, et utiliser une boucle de temps à la place.
- mettre i au nombre premier suivant dans la liste.
Regarde aussi cette question.
Je suis conscient que ce n'est pas une solution rapide.Publication comme solution lente, espérons-le, plus facile à comprendre.
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;
}
Approche itérative Python en supprimant tous les facteurs premiers du nombre
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
J'utilise un algorithme qui continue de diviser le nombre par son facteur premier actuel.
Ma solution en 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())))
Saisir : 10Sortir : 5
Saisir : 600851475143 Sortir : 6857
Voici ma tentative en c#.La dernière impression est le plus grand facteur premier du nombre.J'ai vérifié et ça marche.
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
Calcule le plus grand facteur premier d'un nombre en utilisant la récursivité en C++.Le fonctionnement du code est expliqué ci-dessous :
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
}
Voici mon approche pour calculer rapidement le plus grand facteur premier.Il est basé sur des faits modifiés x ne contient pas de facteurs non premiers.Pour y parvenir, nous divisons x dès qu'un facteur est trouvé.Ensuite, il ne reste plus qu’à renvoyer le plus grand facteur.Ce serait déjà premier.
Le code (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
L'algorithme C++ suivant n'est pas le meilleur, mais il fonctionne pour des nombres inférieurs au milliard et est assez rapide
#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;
}
J'ai trouvé cette solution sur le Web par "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;
}
Facteur premier utilisant un tamis :
#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;
}
Il me semble que l’étape n°2 de l’algorithme donné ne sera pas une approche très efficace.Vous ne pouvez raisonnablement vous attendre à ce qu'il soit premier.
De plus, la réponse précédente suggérant le tamis d'Ératosthène est totalement fausse.Je viens d'écrire deux programmes pour factoriser 123456789.L’un était basé sur le Sieve, l’autre était basé sur ce qui suit :
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
Cette version était 90 fois plus rapide que le Sieve.
Le fait est que sur les processeurs modernes, le type d’opération compte bien moins que le nombre d’opérations, sans compter que l’algorithme ci-dessus peut s’exécuter en cache, contrairement au Sieve.Le Sieve utilise de nombreuses opérations supprimant tous les nombres composés.
Notez également que ma division des facteurs au fur et à mesure qu'ils sont identifiés réduit l'espace qui doit être testé.
Calculez d'abord une liste stockant les nombres premiers, par ex.2 3 5 7 11 13 ...
Chaque fois que vous factorisez un nombre premier, utilisez l'implémentation de Triptych mais en itérant cette liste de nombres premiers plutôt que d'entiers naturels.
Avec Java :
Pour int valeurs:
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;
}
Pour long valeurs:
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;
}
Ce n'est probablement pas toujours plus rapide, mais il est plus optimiste de trouver un gros diviseur premier :
Nest ton numéro- Si c'est premier alors
return(N) - Calculer les nombres premiers jusqu'à
Sqrt(N) - Parcourez les nombres premiers par ordre décroissant (le plus grand en premier)
- Si
N is divisible by PrimealorsReturn(Prime)
- Si
Modifier:À l'étape 3, vous pouvez utiliser le tamis d'Eratosthène ou le tamis d'Atkins ou ce que vous voulez, mais le tamis à lui seul ne vous trouvera pas le plus grand facteur premier.(C'est pourquoi je ne choisirais pas le message de SQLMenace comme réponse officielle...)
Je pense qu'il serait bien de stocker quelque part tous les nombres premiers possibles plus petits que n et de simplement les parcourir pour trouver le plus grand diviseur.Vous pouvez obtenir des primes à partir de nombres-premiers.org.
Bien sûr, je suppose que votre nombre n'est pas trop grand :)
Pas le plus rapide mais ça marche !
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;
}
Voici la même fonction@Triptyque fournie en générateur, qui a également été légèrement simplifiée.
def primes(n):
d = 2
while (n > 1):
while (n%d==0):
yield d
n /= d
d += 1
le nombre premier maximum peut alors être trouvé en utilisant :
n= 373764623
max(primes(n))
et une liste de facteurs trouvés en utilisant :
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();
}
