Algorytm znajdowania największego czynnika pierwszego liczby

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) w najgorszym przypadku (gdy wejście jest liczbą pierwszą).

EDIT:
Poniżej znajduje się wersja O(sqrt(n)), zgodnie z sugestią 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ź opiera się na tryptyku ' s, ale znacznie poprawia na nim. Opiera się ona na tym, ż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 na prymat (i nie ma konstrukcji sita) będzie działać szybciej niż ta, która ich używa. Jeśli tak jest, jest to prawdopodobnie najszybszy algorytm tutaj.

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źć po prostu zaczynając od 2 i po prostu kontynuując dzielenie, aż wynik nie będzie wielokrotnością Twojej liczby:

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

Używając tej metody nie musisz obliczać żadnych liczb pierwszych: wszystkie będą liczbami pierwszymi, bazując na fakcie, że już obliczyłeś liczbę tak bardzo, jak to możliwe, ze wszystkimi liczbami poprzedzającymi.

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
    }

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 @ tryptyk odpowiedz, ale też inne. W tym przykładzie lista lub słownik nie jest używany. Kod jest napisany w 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

Najprostszym rozwiązaniem jest para wzajemnie rekurencyjnych funkcji.

Pierwsza funkcja generuje wszystkie liczby pierwsze:

1. zacznij od listy, która składa się z 2 i wszystkich liczb nieparzystych większych niż 2.
2. Usuń wszystkie liczby, które nie są pierwsze. Oznacza to liczby, które nie mają czynników pierwszych (innych niż same siebie). Patrz poniżej.

Druga funkcja zwraca czynniki pierwsze danej liczby n w porządku rosnącym. Strategia jest to próba podzielenia n przez każdą liczbę pierwszą, która mogłaby być jej dzielnikiem:

1. weź listę wszystkich liczb pierwszych w rosnącej kolejności(patrz wyżej).
2. niech p będzie liczbą pierwszą z tej listy, a {[4] } będzie liczbą pierwszą z n/p (Zobacz Krok 1).
   • Jeśli p kwadrat jest większy od naszej liczby n, to n jest liczbą pierwszą. Skończyliśmy.
   • Jeśli p dzieli n, to p jest czynnikiem pierwszorzędowym n. Pozostałe czynniki to ps.
   • inaczej p nie jest pierwszy czynnik n.

Największym współczynnikiem pierwszym n jest ostatnia liczba podana przez drugą funkcję.

Dla wyjaśnienia, oto kod dla 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

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)

Istnieją pewne testy modulo, które są superflous, ponieważ n nigdy nie może być dzielone przez 6, jeśli wszystkie czynniki 2 i 3 zostały usunięte. Możesz pozwolić tylko na primes dla i, co jest pokazane w kilku innych odpowiedzi tutaj.

Rzeczywiście można tu spleść sito Eratostenesa:

• najpierw Utwórz listę liczb całkowitych w górę do sqrt (n).
• W pętli for Zaznacz wszystkie wielokrotności i do nowego sqrt (n) jako nie prime i zamiast tego użyj pętli while.
• set i to the następna liczba pierwsza w lista.

Zobacz też 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 Pythona poprzez usunięcie wszystkich czynników 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

Używam algorytmu, który kontynuuje dzielenie liczby przez bieżący czynnik pierwszy.

Moje rozwiązanie w Pythonie 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 pierwszym czynnikiem liczby. Sprawdziłam 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 współczynnik liczby przy użyciu rekurencji w C++. Działanie kodu jest wyjaśnione 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 x nie zawiera czynników niepierwszych. Aby to osiągnąć, dzielimy x, gdy tylko zostanie znaleziony czynnik. Następnie pozostaje tylko zwrócić największy czynnik. To byłoby 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 sieci 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;
}

Współczynnik Prime przy użyciu Sitka:

#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 danego algorytmu nie będzie aż tak skuteczny. Nie ma pan rozsądnych oczekiwań, że to jest pierwszorzędne.

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

Rzecz w tym, że na nowoczesnych procesorach rodzaj operacji liczy się znacznie mniej niż liczba operacji, nie wspominając o tym, że powyższy algorytm może działać w pamięci podręcznej, Sito nie może. Sito wykorzystuje wiele operacji wykreślających wszystkie liczby złożone.

Zauważ również, że mój podział czynników, jak są one zidentyfikowane zmniejsza przestrzeń, która musi być badana.

Oblicz listę zawierającą pierwsze liczby, np. 2 3 5 7 11 13 ...

Za każdym razem, gdy faktoryzujesz liczbę pierwszą, używaj implementacji przez tryptyk, ale iterację tej listy liczb pierwszych zamiast naturalnych liczb całkowitych.

Z Javą:

Dla int wartoś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 long wartoś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 co do tego, że można znaleźć duży dzielnik prime:

1. N to twoja liczba
2. jeśli jest pierwsza to return(N)
3. Oblicz liczby pierwsze do Sqrt(N)
4. przejdź przez liczby pierwsze w kolejności malejącej (największa pierwsza)
   • If N is divisible by Prime then Return(Prime)

Edit: w kroku 3 możesz użyć sita Eratostenesa lub Sita Atkinsa lub cokolwiek chcesz, ale samo sito nie znajdzie Cię największy czynnik pierwszorzędny. (Dlatego nie wybrałbym postu SQLMenace jako oficjalnej odpowiedzi...)

Myślę, że byłoby dobrze, aby zapisać gdzieś wszystkie możliwe liczby pierwsze mniejsze niż n i po prostu iterować przez nie, aby znaleźć największy dzielnik. Możesz uzyskać 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;
    }

Tutaj jest ta sama funkcja @ tryptyk dostarczana 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

Max prime można następnie znaleźć za pomocą:

n= 373764623
max(primes(n))

I lista czynników znalezionych za pomocą:

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