Algorithme pour trouver Plus grand facteur premier d'un certain nombre

En fait il y a plusieurs manières plus efficaces de trouver des facteurs de grands nombres (pour les plus petits division de première instance qui fonctionne plutôt bien).

Une méthode qui est très rapide si le nombre d'entrée a deux facteurs très près de sa racine carrée est connu comme Factorisation de Fermat. Il rend l'utilisation de l'identité N = (a + b)(a - b) = a^2 - b^2 et est facile à comprendre et à mettre en œuvre. Malheureusement, il n'est pas très rapide en général.

Le plus connu de la méthode de factorisation de nombres jusqu'à 100 chiffres est le Le crible quadratique. Comme un bonus, une partie de l'algorithme est facile à faire avec le traitement en parallèle.

Encore un autre algorithme, j'ai entendu parler de est Pollard Rho algorithme. Ce n'est pas aussi efficace que le Crible Quadratique en général, mais semble être le plus facile à mettre en œuvre.

Une fois que vous avez décidé sur la façon de diviser un nombre à deux facteurs, ici, c'est l'algorithme le plus rapide que je peux penser à trouver le plus grand facteur premier d'un nombre:

Créer une file d'attente de priorité qui, initialement, stocke le nombre lui-même. À chaque itération, vous supprimez le nombre le plus élevé de la file d'attente, et de tenter de diviser en deux facteurs (ne permettant pas de 1 pour ê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.

Ma réponse est basée sur Triptyque's, mais améliore beaucoup de choses sur elle. Il est basé sur le fait qu'au-delà de 2 et 3, tous les nombres premiers 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 du blog expliquant comment cet algorithme fonctionne.

Je crois qu'une méthode dans laquelle il n'est pas nécessaire pour un test de primalité (et pas de tamis de construction) permettrait de courir plus vite qu'un autre qui ne les utiliser. Si c'est le cas, c'est probablement l'algorithme le plus rapide ici.

Tous les numéros peut être exprimé comme le produit de nombres premiers, par exemple:

102 = 2 x 3 x 17
712 = 2 x 2 x 2 x 89

Vous pouvez trouver ces simplement en commençant à 2 et tout simplement de continuer à se diviser jusqu'à ce que le résultat n'est pas un multiple de votre numéro:

712 /2 = 356 .. 356 /2 = 178 .. 178 /2 = 89 .. 89 /89 = 1

utilisant cette méthode, vous n'avez pas à calculer les nombres premiers: ils vont tous être des nombres premiers, basée sur le fait que vous avez déjà des effets industriels le nombre autant que possible, tous les numéros 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.
}

Similaire à @Triptyque de réponse, mais aussi différents. Dans cet exemple de liste ou un 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

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)

Il y a quelques modulo tests de superflu, que n ne peut jamais être divisé par 6 si tous les facteurs 2 et 3 ont été supprimés. Vous ne pouviez vous permettre de nombres premiers pour moi, ce qui est démontré dans plusieurs autres réponses ici.

Vous pourrait en fait s'entrelacer le crible d'Eratosthène ici:

• D'abord créer la liste des entiers jusqu'
  à sqrt(n).
• Dans la boucle de la marque de tous les multiples
  de i jusqu'à la nouvelle sqrt(n) de ne pas
  le premier, et d'utiliser une boucle while à la place.
• ensemble i pour le prochain nombre premier dans
  la liste.

Voir aussi cette question.

Python approche Itérative par la suppression de 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

Ici est une tentative de ma part en c#. La dernière impression est le plus grand facteur premier de le nombre. J'ai vérifié et il fonctionne.

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;
    }

  }
}

Calcule le plus grand facteur premier d'un nombre en utilisant la récursivité en C++. Le travail de la 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
}

Le C++ suivant l'algorithme n'est pas le meilleur, mais il fonctionne pour les nombres inférieurs à un milliard de dollars et son 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;
 }

Le premier facteur à l'aide de 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;
}

Calculer une liste de stocker des nombres premiers de la première, par exemple, 2 3 5 7 11 13 ...

Chaque fois que vous premier factoriser un nombre, utilisez la mise en œuvre par le Triptyque mais en itérant cette liste de nombres premiers plutôt que d'entiers.

Ce n'est probablement pas toujours plus rapide, mais plus optimiste à ce sujet, vous trouverez un grand diviseur premier:

1. N est votre numéro de
2. Si il est premier alors return(N)
3. Calculer les nombres premiers jusqu'à Sqrt(N)
4. Passer par les nombres premiers dans l'ordre décroissant (de la plus grande première)
   • Si N is divisible by Prime puis Return(Prime)

Edit: Dans l'étape 3, vous pouvez utiliser le Crible d'Eratosthène ou un Tamis de l'Atkins, ou ce que vous voulez, mais par lui-même le tamis de ne pas vous trouver le plus grand facteur premier. (C'est pourquoi je ne voudrais pas choisir SQLMenace post comme une réponse officielle...)

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;
    }

#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();
 }