Algorytm znajdowania największego czynnika pierwszego liczby

Jakie jest najlepsze podejście do obliczania największego czynnika pierwszego z liczby?

Myślę, że najbardziej wydajne byłyby następujące:

1. Znajdź najniższą liczbę pierwszą, która dzieli czysto
2. Sprawdź, czy wynik podziału jest liczbą pierwszą
3. Jeśli nie, znajdź następny najniższy
4. Idź do 2.

Opieram to założenie na tym, że łatwiej jest obliczyć małe czynniki pierwsze. Czy to w porządku? Jakie inne podejścia powinienem rozważyć?

Edycja: Teraz zdałem sobie sprawę, że moje podejście jest daremne, jeśli w grze występują więcej niż 2 czynniki pierwsze, ponieważ krok 2 kończy się niepowodzeniem, gdy wynik jest iloczynem dwóch innych liczb pierwszych, dlatego potrzebny jest algorytm rekurencyjny.

Edytuj ponownie: A teraz zdałem sobie sprawę, że to nadal działa, ponieważ ostatnia znaleziona liczba pierwsza musi być najwyższa, dlatego każde dalsze testowanie wyniku niepierwotnego z kroku 2 spowoduje mniejszą liczbę pierwszą.

W rzeczywistości istnieje kilka bardziej efektywnych sposobów znajdowania czynników o dużych liczbach (w przypadku mniejszych podział prób działa dość dobrze).

Jedną z metod, która jest bardzo szybka, jeśli liczba wejściowa ma dwa czynniki bardzo zbliżone do pierwiastka kwadratowego, jest znana jako faktoryzacja Fermata . Wykorzystuje tożsamość N = (a + b) (a - b) = a ^ 2 - b ^ 2 i jest łatwy do zrozumienia i wdrożenia. Niestety ogólnie nie jest bardzo szybki.

Najbardziej znaną metodą faktorowania liczb o długości do 100 cyfr jest sito kwadratowe . Jako bonus część algorytmu można łatwo wykonać przy przetwarzaniu równoległym.

Jeszcze innym algorytmem, o którym słyszałem, jest algorytm Rho Pollarda . Nie jest tak wydajny jak sito Quadratic w ogóle, ale wydaje się, że jest łatwiejszy do wdrożenia.

Gdy zdecydujesz, jak podzielić liczbę na dwa czynniki, oto najszybszy algorytm, jaki mogę wymyślić, aby znaleźć największy czynnik pierwszy z liczby:

Utwórz kolejkę priorytetową, która początkowo przechowuje sam numer. Podczas każdej iteracji usuwasz najwyższą liczbę z kolejki i próbujesz podzielić ją na dwa czynniki (oczywiście nie dopuszczając, aby 1 był jednym z tych czynników). Jeśli ten krok się nie powiedzie, liczba jest pierwsza i masz odpowiedź! W przeciwnym razie dodaj dwa czynniki do kolejki i powtórz.

Oto najlepszy algorytm, jaki znam (w Pythonie)

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

Powyższa metoda działa w O(n)najgorszym przypadku (gdy wejście jest liczbą pierwszą).

EDYCJA:
Poniżej znajduje się O(sqrt(n))wersja, jak sugerowano w komentarzu. Oto kod, jeszcze raz.

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

Moja odpowiedź oparta jest na Tryptyku , ale bardzo się poprawia. Opiera się na fakcie, że poza 2 i 3 wszystkie liczby pierwsze mają postać 6n-1 lub 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;
}

Niedawno napisałem artykuł na blogu wyjaśniający, jak działa ten algorytm.

Zaryzykowałbym, że metoda, w której nie ma potrzeby badania pierwotności (i bez konstrukcji sita), działałaby szybciej niż ta, która wykorzystuje te. W takim przypadku jest to prawdopodobnie najszybszy algorytm.

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

Przykład użycia:

let result = largestPrimeFactor(600851475143);

Oto przykład kodu :

Podobne do odpowiedzi @Triptych, ale także inne. W tym przykładzie nie użyto listy ani słownika. Kod jest napisany w języku Ruby

def largest_prime_factor(number)
  i = 2
  while number > 1
    if number % i == 0
      number /= i;
    else
      i += 1
    end
  end
  return i
end

largest_prime_factor(600851475143)
# => 6857

Wszystkie liczby można wyrazić jako iloczyn liczb pierwszych, np .:

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

Możesz je znaleźć, zaczynając od 2 i po prostu kontynuując dzielenie, aż wynik nie będzie wielokrotnością liczby:

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

korzystając z tej metody nie musisz w rzeczywistości obliczać liczb pierwszych: wszystkie będą liczbami pierwszymi, w oparciu o fakt, że już uwzględniłeś liczbę jak najwięcej ze wszystkimi poprzednimi liczbami.

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
    }

Najprostszym rozwiązaniem jest para wzajemnie rekurencyjnych funkcji.

Pierwsza funkcja generuje wszystkie liczby pierwsze:

1. Zacznij od listy wszystkich liczb naturalnych większych niż 1.
2. Usuń wszystkie liczby, które nie są liczbami pierwszymi. Oznacza to, że liczby, które nie mają czynników pierwszych (innych niż one). Patrz poniżej.

Druga funkcja zwraca pierwsze liczby danej liczby nw porządku rosnącym.

1. Zrób listę wszystkich liczb pierwszych (patrz wyżej).
2. Usuń wszystkie liczby, które nie są czynnikami n.

Największym czynnikiem pierwszym njest ostatnia liczba podana przez drugą funkcję.

Ten algorytm wymaga leniwej listy lub języka (lub struktury danych) z semantyką wywołania na żądanie .

Dla wyjaśnienia, oto jedna (nieefektywna) implementacja powyższego w 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

Przyspieszenie tego jest po prostu sprytniejsze w wykrywaniu liczb pierwszych i / lub czynników n, ale algorytm pozostaje ten sam.

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)

Istnieje kilka testów modulo, które są zbędne, ponieważ n nigdy nie można podzielić przez 6, jeśli wszystkie czynniki 2 i 3 zostaną usunięte. Można zezwolić tylko na liczby pierwsze dla i, co pokazano w kilku innych odpowiedziach tutaj.

Można tutaj właściwie przeplecić sito Eratostenesa:

• Najpierw utwórz listę liczb całkowitych do sqrt (n).
• W pętli for zaznacz wszystkie wielokrotności i aż do nowej sqrt (n) jako nie pierwszej, i zamiast tego użyj pętli while.
• ustaw i na następny numer pierwszy na liście.

Zobacz także to pytanie .

Wiem, że to nie jest szybkie rozwiązanie. Publikowanie jako, miejmy nadzieję, łatwiejsze do zrozumienia powolne rozwiązanie.

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

Podejście iteracyjne w języku Python poprzez usunięcie wszystkich liczb pierwszych z liczby

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

Korzystam z algorytmu, który nadal dzieli liczbę przez jej aktualny współczynnik Prime.

Moje rozwiązanie w 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()))) 

Wejście: 10 Wyjście:5

Wejście: 600851475143 Wyjście:6857

Oto moja próba w c #. Ostatni wydruk jest największym czynnikiem podstawowym liczby. Sprawdziłem i działa.

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

Oblicza największy czynnik pierwszy liczby za pomocą rekurencji w C ++. Działanie kodu wyjaśniono poniżej:

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
}

Oto moje podejście do szybkiego obliczenia największego czynnika pierwszego. Opiera się na fakcie, że zmodyfikowany xnie zawiera czynników innych niż podstawowe. Aby to osiągnąć, dzielimy się, xgdy tylko znajdzie się czynnik. Następnie pozostaje tylko zwrócić największy czynnik. Byłoby to już pierwsze.

Kod (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

Poniższy algorytm C ++ nie jest najlepszy, ale działa dla liczb poniżej miliarda i jest dość szybki

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

Znalazłem to rozwiązanie w Internecie przez „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;
}

Czynnik zalania za pomocą sita:

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

Wydaje mi się, że krok 2 podanego algorytmu nie będzie aż tak efektywnym podejściem. Nie masz uzasadnionych oczekiwań, że jest to liczba pierwsza.

Również poprzednia odpowiedź sugerująca, że ​​sito Eratostenesa jest całkowicie błędna. Właśnie napisałem dwa programy z współczynnikiem 123456789. Jeden opierał się na Sito, drugi na następujących:

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

Ta wersja była 90 razy szybsza niż Sito.

Chodzi o to, że we współczesnych procesorach rodzaj operacji ma znacznie mniejsze znaczenie niż liczba operacji, nie wspominając już o tym, że powyższy algorytm może działać w pamięci podręcznej, a sito nie. Sito wykorzystuje wiele operacji wykreślających wszystkie liczby zespolone.

Zauważ też, że moje czynniki podziału podczas ich identyfikacji zmniejszają przestrzeń, którą należy przetestować.

Najpierw oblicz listę przechowującą liczby pierwsze, np. 2 3 5 7 11 13 ...

Za każdym razem, gdy liczba pierwsza zostanie rozłożona na czynniki pierwsze, użyj implementacji przez tryptyk, ale iterując tę ​​listę liczb pierwszych zamiast liczb całkowitych naturalnych.

Z Javą:

Dla intwartości:

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

Dla longwartości:

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

Prawdopodobnie nie zawsze jest to szybsze, ale bardziej optymistyczne, że znajdujesz duży główny dzielnik:

1. N jest twój numer
2. Jeśli to jest liczba pierwsza, to return(N)
3. Oblicz liczby pierwsze do Sqrt(N)
4. Przejdź przez liczby pierwsze w kolejności malejącej (najpierw największe)
   • Jeśli N is divisible by PrimetakReturn(Prime)

Edycja: W kroku 3 możesz użyć sita Eratostenesa lub sita Atkinsa lub cokolwiek innego, ale samo sito nie znajdzie dla ciebie największego czynnika podstawowego. (Dlatego nie wybrałbym postu SQLMenace jako oficjalnej odpowiedzi ...)

Myślę, że dobrze byłoby przechowywać gdzieś wszystkie możliwe liczby pierwsze mniejsze niż n i po prostu iterować je, aby znaleźć największy dzielnik. Możesz dostać liczby pierwsze z prime-numbers.org .

Oczywiście zakładam, że twój numer nie jest zbyt duży :)

Nie najszybszy, ale działa!

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

Oto ta sama funkcja @ Tryptyk podana jako generator, która również została nieco uproszczona.

def primes(n):
    d = 2
    while (n > 1):
        while (n%d==0):
            yield d
            n /= d
        d += 1

maksymalną liczbę pierwszą można następnie znaleźć za pomocą:

n= 373764623
max(primes(n))

oraz listę czynników znalezionych przy użyciu:

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