Algorytm znajdowania czynników danej liczby. Najkrótsza metoda?

Question

Co może być najprostszą i wydajną logiką, aby dowiedzieć się o czynnikach z danego Numeru. Czy istnieje algorytm, który istnieje, oparty na tym samym.

Właściwie moim prawdziwym problemem jest odkrycie nr. czynników, które istnieją dla danej liczby ..

więc każdy algorytm, proszę dać mi znać o tym ..

Dzięki.

Answer 1

Właściwie moim prawdziwym problemem jest odkrycie nr. czynników istniejących dla danego numeru.

Cóż, jest inaczej. Niech n będzie podaną liczbą.

Jeśli n = p1^e1 * p2^e2 * ... * pk^ek, gdzie każdy p jest liczbą pierwszą, to liczba czynników n jest (e1 + 1)*(e2 + 1)* ... *(ek + 1). Więcej na ten temat here.

Dlatego wystarczy znaleźć moce, w których pojawia się każdy czynnik główny. Na przykład:

read given number in n 
initial_n = n 
num_factors = 1; 
for (i = 2; i * i <= initial_n; ++i) // for each number i up until the square root of the given number 
{ 
    power = 0; // suppose the power i appears at is 0 
    while (n % i == 0) // while we can divide n by i 
    { 
     n = n/i // divide it, thus ensuring we'll only check prime factors 
     ++power // increase the power i appears at 
    } 
    num_factors = num_factors * (power + 1) // apply the formula 
} 

if (n > 1) // will happen for example for 14 = 2 * 7 
{ 
    num_factors = num_factors * 2 // n is prime, and its power can only be 1, so multiply the number of factors by 2 
} 

Na przykład weź 18. 18 = 2^1 * 3*2 => number of factors = (1 + 1)*(2 + 1) = 6. Rzeczywiście, współczynniki 6 z 18 są .

Oto mały benchmark między moją metodą a metodą opisaną i opublikowaną przez @Maciej. Jego ma tę zaletę, że jest łatwiejsza do wykonania, natomiast kopalnia ma tę zaletę, że szybciej, jeśli zmiana tylko iterację ciągu liczb, jak Ja wam uczyniłem dla tego testu:

class Program 
{ 
    static private List<int> primes = new List<int>(); 

    private static void Sieve() 
    { 
     bool[] ok = new bool[2000]; 

     for (int i = 2; i < 2000; ++i) // primes up to 2000 (only need up to sqrt of 1 000 000 actually) 
     { 
      if (!ok[i]) 
      { 
       primes.Add(i); 

       for (int j = i; j < 2000; j += i) 
        ok[j] = true; 
      } 
     } 
    } 

    private static int IVlad(int n) 
    { 
     int initial_n = n; 
     int factors = 1; 

     for (int i = 0; primes[i] * primes[i] <= n; ++i) 
     { 
      int power = 0; 
      while (initial_n % primes[i] == 0) 
      { 
       initial_n /= primes[i]; 
       ++power; 
      } 
      factors *= power + 1; 
     } 

     if (initial_n > 1) 
     { 
      factors *= 2; 
     } 

     return factors; 
    } 

    private static int Maciej(int n) 
    { 
     int factors = 1; 
     int i = 2; 
     for (; i * i < n; ++i) 
     { 
      if (n % i == 0) 
      { 
       ++factors; 
      } 
     } 

     factors *= 2; 

     if (i * i == n) 
     { 
      ++factors; 
     } 

     return factors; 
    } 

    static void Main() 
    { 
     Sieve(); 


     Console.WriteLine("Testing equivalence..."); 

     for (int i = 2; i < 1000000; ++i) 
     { 
      if (Maciej(i) != IVlad(i)) 
      { 
       Console.WriteLine("Failed!"); 
       Environment.Exit(1); 
      } 
     } 

     Console.WriteLine("Equivalence confirmed!"); 

     Console.WriteLine("Timing IVlad..."); 
     Stopwatch t = new Stopwatch(); 

     t.Start(); 
     for (int i = 2; i < 1000000; ++i) 
     { 
      IVlad(i); 
     } 

     Console.WriteLine("Total milliseconds: {0}", t.ElapsedMilliseconds); 
     Console.WriteLine("Timing Maciej..."); 

     t.Reset(); 
     t.Start(); 
     for (int i = 2; i < 1000000; ++i) 
     { 
      Maciej(i); 
     } 


     Console.WriteLine("Total milliseconds: {0}", t.ElapsedMilliseconds); 
    } 
} 

wyników na moim komputerze:

Równoważność testowania ...
Równoważność potwierdzona!
Timing IVlad ...
Wszystkich milisekund: 2448
Timing Maciej ...
Wszystkich milisekund: 3951
Naciśnij dowolny klawisz, aby kontynuować. . .

Answer 2

Możesz rzucić okiem na this algorithm.

Answer 3

Dostępnych jest wiele algorytmów - od prostego opracowywania prób do bardzo zaawansowanych algorytmów dla dużych liczb. Spójrz na Integer Factorization na Wikipedii i wybierz taki, który odpowiada Twoim potrzebom.

Oto krótka, ale nieefektywna implementacja C#, która określa liczbę czynników pierwszych. Jeśli potrzebujesz liczby czynników (nie czynników pierwszeństwa), musisz przechowywać czynniki pierwsze z ich licznością i obliczyć liczbę czynników później.

var number = 3 * 3 * 5 * 7 * 11 * 11; 

var numberFactors = 0; 
var currentFactor = 2; 

while (number > 1) 
{ 
    if (number % currentFactor == 0) 
    { 
     number /= currentFactor; 
     numberFactors++; 
    } 
    else 
    { 
     currentFactor++; 
    } 
} 

Answer 4

Algorytm Euclida powinien wystarczyć.

Answer 5

Oto owoc mojej krótkiej dyskusji z |/| reklamie :)

read given number in n 
int divisorsCount = 1; 
int i; 
for(i = 2; i * i < n; ++i) 
{ 
    if(n % i == 0) 
    { 
     ++divisorsCount; 
    } 
} 
divisorsCount *= 2; 
if(i * i == n) 
{ 
    ++divisorsCount; 
} 

Answer 6

Ostrożnie, ta odpowiedź jest nieprzydatne/szybki dla pojedynczej wartości n.

Metoda 1:

można dostać w czasie O (polylog (n)) jeśli utrzymanie tabelę przeglądową (dla pierwszego głównego czynnika liczbę).

Jeśli gcd (a, b) == 1, to nie. współczynników a * b = (liczba czynników a) * (liczba czynników b)

Dlatego dla danej liczby a * b, jeśli gcd (a, b)! = 1 to może mieć dwie inne liczby p i q, gdzie p = a i q = b/gcd (a, b). Zatem gcd (p, q) == 1. Teraz możemy rekursywnie znaleźć liczbę czynników dla p i q.

To zajmie tylko jakąś małą ilość wysiłków zmierzających do zapewnienia ani p, ani q wynosi 1.

PS: Ta metoda jest również przydatna, gdy musisz znać liczbę czynników wszystkich liczb od 1 do n. Byłaby to kolejność O (nlogn + O (tabela przeglądowa)).

Metoda 2 (nie mam prawa własności do tego.)

Jeśli masz przeglądowej dla pierwszego czynnika głównego aż do n, to możesz wiedzieć, że to wszystkich czynników w czasie O (logn) i w ten sposób znaleźć liczbę czynników z nich.

P.S. Google "Faktoryzacja w logn" dla lepszego wyjaśnienia.