Algorytm znajdowania największego czynnika pierwszego liczby


183

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ą.


Moje podejście było następujące: (1) podziel dużą, możliwą liczbę przez 2; (2) sprawdź, czy duża liczba dzieli się na nią równomiernie; (3) jeśli tak, sprawdź, czy liczba podzielona przez 2 jest liczbą pierwszą. Jeśli tak, zwróć go. (4) W przeciwnym razie odejmij 1 od podzielonej przez 2 liczby, wracając do kroku 3.
Kevin Meredith

1.znajdź dowolną liczbę, która wyraźnie dzieli (dla i = 2 do int (sqr (num))) 2.podziel przez tę liczbę (num = num / i) i powtarzaj się, dopóki nic nie zostanie znalezione w 1. interwał 3. num jest największym czynnikiem
użytkownik3819867

1
Możemy dzielić za pomocą małych liczb pierwszych, a ten, który w końcu został, to największy czynnik

Odpowiedzi:


134

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.


3
Metoda Pollarda rho i metoda krzywej eliptycznej są znacznie lepsze w usuwaniu małych czynników pierwszych z twojej liczby niż sito kwadratowe. QS ma prawie taki sam czas działania bez względu na liczbę. To, które podejście jest szybsze, zależy od tego, jaki jest twój numer; QS będzie szybciej łamać liczby trudne do faktoryzacji, podczas gdy rho i ECM będą szybciej łamać liczby trudne do faktoryzacji.
tmyklebu

Dziękujemy za sugestię odmiany kwadratowej. Musiałem to zaimplementować dla jednego z moich klientów, początkowa wersja, którą wymyśliłem, była czymś podobnym do sugestii @mercutio w jego pytaniu. Kwadratyczne rozwiązanie napędza teraz narzędzie mojego klienta na stronie math.tools/calculator/prime-factors .
dors

Jeśli istnieje skuteczny sposób rozwiązania tego problemu, czy nie oznacza to, że szyfrowanie sieciowe nie jest bezpieczne?
BKSpurgeon

141

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

11
Przeczytaj ten kod i / lub uruchom go przed głosowaniem. To działa dobrze. Po prostu skopiuj i wklej. Jak napisano, prime_factors (1000) zwróci [2,2,2,5,5,5], co należy interpretować jako 2 ^ 3 * 5 ^ 3, czyli rozkład na czynniki pierwsze.
Tryptyk

11
„wpada w O(sqrt(n))najgorszym przypadku” - Nie, wpada w O(n)najgorszym przypadku (np. kiedy njest pierwsza).
Sheldon L. Cooper

16
Łatwo zrobić to O (sqrt (n)), po prostu zatrzymaj pętlę, gdy d * d> n, a jeśli n> 1 w tym momencie, to jej wartość powinna zostać dołączona do listy czynników pierwszych.
Sumudu Fernando

5
Czy jest na to jakaś nazwa?
Myśliciel

11
ponieważ 2 jest jedyną parzystą liczbą pierwszą, więc zamiast dodawać 1 za każdym razem, możesz iterować osobno dla d = 2, a następnie zwiększać ją o 1, a następnie od d = 3 możesz zwiększać o 2, aby zmniejszyć liczbę iteracji ... :)
tailor_raj

18

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.


12
Możesz faktycznie posunąć ten pomysł jeszcze dalej, np. Powyżej 2,3,5 wszystkie liczby pierwsze mają postać 30n + k (n> = 0), gdzie k przyjmuje tylko te wartości z przedziału od 1 do 29, które nie są podzielne przez 2,3 lub 5, tj. 7,11,13,17,19,23,29. Możesz nawet to dynamicznie dostosować po każdych kilku liczbach pierwszych, które znalazłeś do 2 * 3 * 5 * 7 * ... * n + k, gdzie k nie może być podzielne przez żadną z tych liczb pierwszych (zauważ, że nie wszystkie możliwe k potrzebują bądź najlepszy, np. dla 210n + k musisz podać 121, w przeciwnym razie przegapisz 331 )
Tobias Kienzler

2
Myślę, że tak powinno byćwhile (multOfSix - 1 <= n)
Nader Ghanbari

8

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 :


7

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

Wreszcie coś czytelnego i natychmiastowego (w js) wykonywalnego w tym samym czasie. Próbowałem użyć nieskończonej listy liczb pierwszych i było już zbyt wolno na 1 milion.
Ebuall,

4

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

Tak, ale jest to okropnie nieefektywne. Po podzieleniu wszystkich 2 sekund, naprawdę nie powinieneś próbować dzielić przez 4, 6, lub ...; Jest to o wiele bardziej wydajne w limicie, aby sprawdzać tylko liczby pierwsze lub użyć jakiegoś innego algorytmu.
wnoise

6
+1, aby zrównoważyć wnoise, który moim zdaniem jest błędny. Próba podzielenia przez 4 nastąpi tylko raz i natychmiast się nie powiedzie. Nie sądzę, że jest to gorsze niż usunięcie 4 z jakiejś listy kandydatów i jest to z pewnością szybsze niż znalezienie wszystkich liczb pierwszych.
Tryptyk

2
@Beowulf. Spróbuj uruchomić ten kod, zanim zagłosujesz. Zwraca czynniki pierwsze; po prostu nie rozumiesz algorytmu.
Tryptyk

3
kod działa poprawnie, ale jest powolny, jeśli liczba przychodząca jest liczbą pierwszą. Podbiegłbym też tylko do kwadratu i zwiększyłbym się o 2. To może być jednak zbyt wolne dla bardzo dużych liczb.
blabla999

4
Blabla999 ma dokładnie rację. Przykładem jest 1234567898766700 = 2 * 2 * 5 * 5 * 12345678987667. Po osiągnięciu currFactor = 3513642celu wiemy, że 12345678987667 jest liczbą pierwszą i powinniśmy go zwrócić jako odpowiedź. Zamiast tego ten kod będzie kontynuował wyliczanie do samego 12345678987667. To 3,533,642x wolniej niż to konieczne.
Will Ness,

4
    //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
    }

1
wypróbowałeś swój kod z 1 000 000 000 039? powinien też działać w mgnieniu oka. Czy to?
Czy Ness

2
Możesz to wiedzieć z góry, bez próbowania. 10 ^ 12 = (2 * 5) ^ 12 = 2 ^ 12 * 5 ^ 12. Twoja whilepętla przejdzie przez iwartości 2,2,2,2,2,2,2,2,2,2,2,2, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5. Wszystkie 60 iteracji. Jednak dla 10 (^ 12 + 39) będzie (10 ^ 12 + 38) iteracji i=2,3,4,5,6,...,10^12+39. Nawet jeśli 10 ^ 10 operacji zajmie jedną sekundę, 10 ^ 12 zajmie 100 sekund. Ale tak naprawdę potrzebne są tylko 10 ^ 6 iteracji, a jeśli 10 ^ 10 operacji zajmie sekundę, 10 ^ 6 zajmie 1/10 000 tysięcznej sekundy.
Czy Ness

1
Ponieważ nie zdawałem sobie sprawy (10 ^ 12 + 39) jest liczbą pierwszą, którą teraz robię. Rozumiem dokładnie to, co mówisz.
the_prole

1
OK, więc możesz zmienić kod, aby nie było tak dużego spowolnienia dla liczb pierwszych: jeśli n = a bi <a b, to a a <= b a = n, tj. A a <= n . A jeśli osiągnęliśmy +1, to n jest z pewnością liczbą pierwszą. (pinguj mnie, jeśli edytujesz swoją odpowiedź, aby to uwzględnić).
Czy Ness

1
co się dzieje, kiedy long n = 2*1000000000039L? Czy działa tak szybko, jak powinien? (możesz też uprościć kod za pomocą return;instrukcji?). (jeśli chcesz, żebym przestał cię szturchać, po prostu to powiedz;))
Czy Ness

4

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.


2
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 .


2

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

1

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

1

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


0

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

  }
}

0
#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

1
czy 25 jest największym współczynnikiem podstawowym wynoszącym 25?
Czy Ness

0

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
}

0

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

ale czy to też nie będzie próbowało podzielić wszystkich liczb parzystych?
Janus Troelsen

0

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

0

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

0

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

-1

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ć.


to właśnie powiedziałem, ale zostałem odrzucony :( Myślę, że problem polega na tym, że jeśli liczba ma naprawdę duży czynnik pierwszy (taki jak ona sama), to ta metoda musi zapętlić się aż do tej liczby. W wielu przypadkach jednak ta metoda jest dość wydajna
nickf

Czytanie przez ciebie jest takie samo, ale pierwsza część jest myląca.
Loren Pechtel

Spróbuj tego pod tym numerem 143816789988504044536402352738195137863656439, daj mi znać, jak to jest wydajne ...
MichaelICE

-1

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.


-1

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

-2

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 ...)


1
Czy nie musisz przeprowadzać faktoringu próbnego, aby ustalić, czy jest to liczba pierwsza (krok 2)? Rozważ też znalezienie największego czynnika pierwszego wynoszącego 15. Liczby pierwsze do sqrt (15) to 2 i 3; ale największy czynnik pierwszy to 5, prawda? Podobnie z 20.
Jonathan Leffler

-3

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 :)


-3

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

To nie jest odpowiedź na pytanie. ;-) Pytanie dotyczyło znalezienia największego czynnika pierwszego, a nie sprawdzenia pierwszeństwa.
Hans-Peter Störr

O wiele bardziej wydajne jest inicjowanie pętli jako (długie i = 3; i <checkUpTo; i + = 2)
cjk

-3

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))

-6
#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();
 }
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.