Jaki byłby najbardziej optymalny algorytm (pod względem wydajności) do obliczenia liczby dzielników podanej liczby?

Byłoby wspaniale, gdybyś mógł podać pseudokod lub link do jakiegoś przykładu.

EDYCJA: Wszystkie odpowiedzi były bardzo pomocne, dziękuję. Wdrażam Sieve of Atkin, a potem zamierzam użyć czegoś podobnego do tego, co wskazał Jonathan Leffler. Link zamieszczony przez Justina Bozoniera zawiera dalsze informacje o tym, czego chciałem.

Dmitriy ma rację, że chcesz, aby Sieve of Atkin wygenerowała pierwszą listę, ale nie sądzę, aby to załatwiło całą sprawę. Teraz, gdy masz już listę liczb pierwszych, musisz zobaczyć, ile z tych liczb pierwszych działa jako dzielnik (i jak często).

Oto python dla algo. Szukaj tutaj i wyszukaj „Temat: matematyka - algorytm potrzeb dzielników”. Po prostu policz liczbę pozycji na liście, zamiast je zwracać.

Oto Dr. Math, który wyjaśnia, co dokładnie musisz zrobić matematycznie.

Zasadniczo sprowadza się to do tego, że jeśli twoja liczba nto:
n = a^x * b^y * c^z
(gdzie a, b i c są pierwszymi dzielnikami n, a x, y i z to liczba powtórzeń dzielnika), to całkowita liczba wszystkich dzielników wynosi:
(x + 1) * (y + 1) * (z + 1).

Edycja: BTW, aby znaleźć a, b, c, itd., Będziesz chciał zrobić coś, co sprowadza się do chciwego algo, jeśli dobrze to rozumiem. Zacznij od największego dzielnika pierwszego i pomnóż go przez siebie, aż dalsze pomnożenie przekroczy liczbę n. Następnie przejdź do następnego najniższego współczynnika i razy poprzedniej liczby pierwszej ^ ile razy została pomnożona przez aktualną liczbę pierwszą i kontynuuj mnożenie przez liczbę pierwszą, aż następny przekroczy n ... itd. Śledź, ile razy pomnożyłeś dzielniki razem i zastosuj te liczby do powyższego wzoru.

Nie jestem w 100% pewien co do mojego opisu algo, ale jeśli to nie jest to, to coś podobnego.

Istnieje o wiele więcej technik faktorowania niż sito Atkina. Na przykład przypuśćmy, że chcemy podzielić na czynniki 5893. Cóż, jego sqrt to 76,76 ... Teraz spróbujemy zapisać 5893 jako iloczyn kwadratów. Cóż (77 * 77 - 5893) = 36, czyli 6 do kwadratu, więc 5893 = 77 * 77 - 6 * 6 = (77 + 6) (77-6) = 83 * 71. Gdyby to nie zadziałało, sprawdzilibyśmy, czy 78 * 78 - 5893 to idealny kwadrat. I tak dalej. Dzięki tej technice możesz szybko przetestować czynniki w pobliżu pierwiastka kwadratowego z n znacznie szybciej niż testując pojedyncze liczby pierwsze. Jeśli połączysz tę technikę wykluczania dużych liczb pierwszych z sitem, uzyskasz znacznie lepszą metodę faktoryzacji niż w przypadku samego sita.

A to tylko jedna z wielu opracowanych technik. To jest dość proste. Zajęłoby ci dużo czasu, aby nauczyć się, powiedzmy, wystarczającej teorii liczb, aby zrozumieć techniki faktoryzacji oparte na krzywych eliptycznych. (Wiem, że istnieją. Nie rozumiem ich.)

Dlatego jeśli nie masz do czynienia z małymi liczbami całkowitymi, nie próbowałbym sam rozwiązać tego problemu. Zamiast tego spróbuję znaleźć sposób na użycie czegoś takiego jak biblioteka PARI, która ma już wdrożone wysoce wydajne rozwiązanie. Dzięki temu mogę rozliczyć losową 40-cyfrową liczbę, taką jak 124321342332143213122323434312213424231341 w około 0,05 sekundy. (Jego faktoryzacja, na wypadek, gdybyś się zastanawiała, wynosi 29 * 439 * 1321 * 157907 * 284749 * 33843676813 * 4857795469949. Jestem całkiem pewien, że nie doszedł do tego za pomocą sita Atkina ...)

@Yasky

Twoja funkcja dzielników ma błąd polegający na tym, że nie działa poprawnie dla idealnych kwadratów.

Próbować:

int divisors(int x) {
    int limit = x;
    int numberOfDivisors = 0;

    if (x == 1) return 1;

    for (int i = 1; i < limit; ++i) {
        if (x % i == 0) {
            limit = x / i;
            if (limit != i) {
                numberOfDivisors++;
            }
            numberOfDivisors++;
        }
    }

    return numberOfDivisors;
}

Nie zgadzam się, że sito Atkina jest drogą do zrobienia, ponieważ sprawdzenie każdej liczby w [1, n] może zająć więcej czasu niż zmniejszenie liczby o podziały.

Oto kod, który, choć nieco bardziej skomplikowany, jest generalnie znacznie szybszy:

import operator
# A slightly efficient superset of primes.
def PrimesPlus():
  yield 2
  yield 3
  i = 5
  while True:
    yield i
    if i % 6 == 1:
      i += 2
    i += 2
# Returns a dict d with n = product p ^ d[p]
def GetPrimeDecomp(n):
  d = {}
  primes = PrimesPlus()
  for p in primes:
    while n % p == 0:
      n /= p
      d[p] = d.setdefault(p, 0) + 1
    if n == 1:
      return d
def NumberOfDivisors(n):
  d = GetPrimeDecomp(n)
  powers_plus = map(lambda x: x+1, d.values())
  return reduce(operator.mul, powers_plus, 1)

ps To działający kod w Pythonie, który rozwiązuje ten problem.

Oto prosty algorytm O (sqrt (n)). Użyłem tego do rozwiązania projektu euler

def divisors(n):
    count = 2  # accounts for 'n' and '1'
    i = 2
    while i ** 2 < n:
        if n % i == 0:
            count += 2
        i += 1
    if i ** 2 == n:
        count += 1
    return count

To interesujące pytanie jest o wiele trudniejsze, niż się wydaje, i nie ma na nie odpowiedzi. Pytanie można rozłożyć na 2 bardzo różne pytania.

1 mając N, znajdź listę L czynników pierwszych N.

2 biorąc pod uwagę L, oblicz liczbę unikalnych kombinacji

Wszystkie odpowiedzi, które do tej pory widzę, odnoszą się do nr 1 i nie wspominają, że nie da się tego rozwiązać w przypadku ogromnych liczb. Dla średniej wielkości N, nawet 64-bitowych, jest to łatwe; dla ogromnego N problem faktoringu może trwać „wiecznie”. Od tego zależy szyfrowanie klucza publicznego.

Pytanie nr 2 wymaga dalszej dyskusji. Jeśli L zawiera tylko unikalne liczby, jest to proste obliczenie przy użyciu wzoru kombinacji do wyboru k obiektów z n elementów. W rzeczywistości należy zsumować wyniki zastosowania wzoru, zmieniając k od 1 do sizeof (L). Jednak L zwykle zawiera wiele wystąpień wielu liczb pierwszych. Na przykład L = {2,2,2,3,3,5} to faktoryzacja N = 360. Teraz ten problem jest dość trudny!

Powtarzając # 2, dany zbiór C zawiera k elementów, tak że element a ma „duplikaty, a element b ma duplikaty b” itd. Ile jest unikalnych kombinacji elementów od 1 do k-1? Na przykład {2}, {2,2}, {2,2,2}, {2,3}, {2,2,3,3} muszą wystąpić raz i tylko raz, jeśli L = {2,2 , 2,3,3,5}. Każda taka unikalna pod-kolekcja jest niepowtarzalnym dzielnikiem N przez pomnożenie elementów w pod-kolekcji.

Odpowiedź na twoje pytanie zależy w dużej mierze od wielkości liczby całkowitej. Metody dla małych liczb, np. Mniejszych niż 100 bitów i dla liczb ~ 1000 bitów (takich jak stosowane w kryptografii) są zupełnie inne.

• ogólny przegląd: http://en.wikipedia.org/wiki/Divisor_function

• wartości małych ni przydatnych odniesień: A000005: d (n) (zwane również tau (n) lub sigma_0 (n)), liczba dzielników n.

• przykład ze świata rzeczywistego: faktoryzacja liczb całkowitych

TYLKO jedna linia
Bardzo uważnie przemyślałem twoje pytanie i próbowałem napisać bardzo wydajny i wydajny fragment kodu. Aby wypisać na ekranie wszystkie dzielniki danej liczby, potrzebujemy tylko jednej linii kodu! (użyj opcji -std = c99 podczas kompilacji przez gcc)

for(int i=1,n=9;((!(n%i)) && printf("%d is a divisor of %d\n",i,n)) || i<=(n/2);i++);//n is your number

aby znaleźć liczby dzielników, możesz użyć następującej bardzo szybkiej funkcji (działa poprawnie dla wszystkich liczb całkowitych z wyjątkiem 1 i 2)

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return counter;
}

lub jeśli traktujesz podaną liczbę jako dzielnik (działa poprawnie dla wszystkich liczb całkowitych z wyjątkiem 1 i 2)

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return ++counter;
}

UWAGA: dwie powyższe funkcje działają poprawnie dla wszystkich dodatnich liczb całkowitych z wyjątkiem liczb 1 i 2, więc działają one dla wszystkich liczb, które są większe niż 2, ale jeśli potrzebujesz pokryć 1 i 2, możesz użyć jednej z następujących funkcji (trochę wolniej)

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    if (n==2 || n==1)
    {
    return counter;
    }
    return ++counter;
}

LUB

int number_of_divisors(int n)
{
    int counter,i;
for(counter=0,i=1;(!(i==n) && !(n%i) && (counter++)) || i<=(n/2);i++);
    return ++counter;
}

małe jest piękne :)

Sito Atkina jest zoptymalizowaną wersją sita Eratostenesa, które podaje wszystkie liczby pierwsze aż do podanej liczby całkowitej. Powinieneś być w stanie znaleźć to w Google, aby uzyskać więcej szczegółów.

Gdy masz już tę listę, łatwo jest podzielić swoją liczbę przez każdą liczbę pierwszą, aby sprawdzić, czy jest to dokładny dzielnik (tj. Reszta to zero).

Podstawowe kroki obliczania dzielników dla liczby (n) to [to jest pseudokod przekonwertowany z prawdziwego kodu, więc mam nadzieję, że nie wprowadziłem błędów]:

for z in 1..n:
    prime[z] = false
prime[2] = true;
prime[3] = true;

for x in 1..sqrt(n):
    xx = x * x

    for y in 1..sqrt(n):
        yy = y * y

        z = 4*xx+yy
        if (z <= n) and ((z mod 12 == 1) or (z mod 12 == 5)):
            prime[z] = not prime[z]

        z = z-xx
        if (z <= n) and (z mod 12 == 7):
            prime[z] = not prime[z]

        z = z-yy-yy
        if (z <= n) and (x > y) and (z mod 12 == 11):
            prime[z] = not prime[z]

for z in 5..sqrt(n):
    if prime[z]:
        zz = z*z
        x = zz
        while x <= limit:
            prime[x] = false
            x = x + zz

for z in 2,3,5..n:
    if prime[z]:
        if n modulo z == 0 then print z

Możesz spróbować tego. To trochę hakerskie, ale dość szybkie.

def factors(n):
    for x in xrange(2,n):
        if n%x == 0:
            return (x,) + factors(n/x)
    return (n,1)

Gdy masz już rozkład na czynniki pierwsze, istnieje sposób na znalezienie liczby dzielników. Dodaj po jednym do każdego wykładnika każdego czynnika, a następnie pomnóż wykładniki razem.

Na przykład: 36 Rozkład na czynniki pierwsze: 2 ^ 2 * 3 ^ 2 Dzielniki: 1, 2, 3, 4, 6, 9, 12, 18, 36 Liczba dzielników: 9

Dodaj po jednym do każdego wykładnika 2 ^ 3 * 3 ^ 3 Pomnóż wykładniki: 3 * 3 = 9

Zanim zdecydujesz się na rozwiązanie, weź pod uwagę, że podejście Sieve może nie być dobrą odpowiedzią w typowym przypadku.

Jakiś czas temu pojawiło się pierwsze pytanie i zrobiłem test czasu - dla 32-bitowych liczb całkowitych przynajmniej określenie, czy jest to liczba pierwsza, było wolniejsze niż brutalna siła. Istnieją dwa czynniki:

1) Podczas gdy człowiekowi zajmuje się trochę czasu, aby dokonać podziału, jest on bardzo szybki na komputerze - podobnie jak koszt szukania odpowiedzi.

2) Jeśli nie masz tabeli głównej, możesz utworzyć pętlę działającą w całości w pamięci podręcznej L1. To sprawia, że ​​jest szybszy.

To wydajne rozwiązanie:

#include <iostream>
int main() {
  int num = 20; 
  int numberOfDivisors = 1;

  for (int i = 2; i <= num; i++)
  {
    int exponent = 0;
    while (num % i == 0) {
        exponent++; 
        num /= i;
    }   
    numberOfDivisors *= (exponent+1);
  }

  std::cout << numberOfDivisors << std::endl;
  return 0;
}

Dzielniki robią coś spektakularnego: całkowicie dzielą. Jeśli chcesz sprawdzić liczbę dzielników dla wielu, nto wyraźnie jest zbędne obejmować całe spektrum, 1...n. Nie przeprowadziłem żadnych szczegółowych badań, ale rozwiązałem problem 12 projektu Eulera dotyczący liczb trójkątnych . Moje rozwiązanie dla testu dzielników większych niż 500 działało przez 309504 mikrosekund (~ 0,3 s). Napisałem tę funkcję dzielnika dla rozwiązania.

int divisors (int x) {
    int limit = x;
    int numberOfDivisors = 1;

    for (int i(0); i < limit; ++i) {
        if (x % i == 0) {
            limit = x / i;
            numberOfDivisors++;
        }
    }

    return numberOfDivisors * 2;
}

Każdy algorytm ma słaby punkt. Myślałem, że to słabe w porównaniu z liczbami pierwszymi. Ale ponieważ liczby trójkątne nie są drukowane, spełniło swoje zadanie bezbłędnie. Sądząc po moim profilowaniu, myślę, że wyszło całkiem nieźle.

Wesołych Świąt.

Chcesz Sieve of Atkin, opisaną tutaj: http://en.wikipedia.org/wiki/Sieve_of_Atkin

metoda liczb pierwszych jest tutaj bardzo jasna. P [] jest listą liczb pierwszych mniejszych lub równych sq = sqrt (n);

for (int i = 0 ; i < size && P[i]<=sq ; i++){
          nd = 1;
          while(n%P[i]==0){
               n/=P[i];
               nd++;
               }
          count*=nd;
          if (n==1)break;
          }
      if (n!=1)count*=2;//the confusing line :D :P .

     i will lift the understanding for the reader  .
     i now look forward to a method more optimized  .

Podręczniki teorii liczb nazywają funkcję liczenia dzielników tau. Pierwszym interesującym faktem jest to, że jest multiplikatywny, tj. τ (ab) = τ (a) τ (b), gdy a i b nie mają wspólnego dzielnika. (Dowód: każda para dzielników a i b daje odrębny dzielnik ab).

Teraz zauważ, że dla pa prim, τ (p ** k) = k + 1 (potęgi p). W ten sposób możesz łatwo obliczyć τ (n) na podstawie jego faktoryzacji.

Jednak faktoryzacja dużych liczb może być powolna (bezpieczeństwo kryptografii RSA zależy od iloczynu dwóch dużych liczb pierwszych, które są trudne do faktoryzacji). To sugeruje ten zoptymalizowany algorytm

1. Sprawdź, czy liczba jest pierwsza (szybka)
2. Jeśli tak, zwróć 2
3. W przeciwnym razie faktoryzuj liczbę (powoli, jeśli jest wiele dużych czynników pierwszych)
4. Oblicz τ (n) na podstawie faktoryzacji

Poniżej znajduje się program w C do znajdowania liczby dzielników podanej liczby.

Złożoność powyższego algorytmu wynosi O (sqrt (n)).

Algorytm ten będzie działał poprawnie dla liczb, które są idealnie kwadratowe, a także dla liczb, które nie są idealnie kwadratowe.

Zauważ, że górny limit pętli jest ustawiony na pierwiastek kwadratowy z liczby, aby algorytm był najbardziej wydajny.

Zauważ, że przechowywanie górnego limitu w oddzielnej zmiennej również oszczędza czas, nie powinieneś wywoływać funkcji sqrt w sekcji warunków pętli for, oszczędza to również czas obliczeniowy.

#include<stdio.h>
#include<math.h>
int main()
{
    int i,n,limit,numberOfDivisors=1;
    printf("Enter the number : ");
    scanf("%d",&n);
    limit=(int)sqrt((double)n);
    for(i=2;i<=limit;i++)
        if(n%i==0)
        {
            if(i!=n/i)
                numberOfDivisors+=2;
            else
                numberOfDivisors++;
        }
    printf("%d\n",numberOfDivisors);
    return 0;
}

Zamiast powyższej pętli for możesz również użyć następującej pętli, która jest jeszcze bardziej wydajna, ponieważ eliminuje potrzebę znajdowania pierwiastka kwadratowego z liczby.

for(i=2;i*i<=n;i++)
{
    ...
}

Oto funkcja, którą napisałem. jego najgorsza złożoność czasowa to O (sqrt (n)), natomiast najlepszy czas to O (log (n)). Daje wszystkie pierwsze dzielniki wraz z liczbą ich wystąpień.

public static List<Integer> divisors(n) {   
    ArrayList<Integer> aList = new ArrayList();
    int top_count = (int) Math.round(Math.sqrt(n));
    int new_n = n;

    for (int i = 2; i <= top_count; i++) {
        if (new_n == (new_n / i) * i) {
            aList.add(i);
            new_n = new_n / i;
            top_count = (int) Math.round(Math.sqrt(new_n));
            i = 1;
        }
    }
    aList.add(new_n);
    return aList;
}

Oto najbardziej podstawowy sposób obliczania dzielników liczb:

class PrintDivisors
{
    public static void main(String args[])
    {

    System.out.println("Enter the number");

    // Create Scanner object for taking input
    Scanner s=new Scanner(System.in);

    // Read an int
    int n=s.nextInt();

        // Loop from 1 to 'n'
        for(int i=1;i<=n;i++)
        {

            // If remainder is 0 when 'n' is divided by 'i',
            if(n%i==0)
            {
            System.out.print(i+", ");
            }
        }

    // Print [not necessary]    
    System.out.print("are divisors of "+n);

    }
}

@Kendall

Przetestowałem Twój kod i wprowadziłem kilka ulepszeń, teraz jest jeszcze szybszy. Testowałem również z kodem @ هومن جاویدپور, jest to również szybsze niż jego kod.

long long int FindDivisors(long long int n) {
  long long int count = 0;
  long long int i, m = (long long int)sqrt(n);
  for(i = 1;i <= m;i++) {
    if(n % i == 0)
      count += 2;
  }
  if(n / m == m && n % m == 0)
    count--;
  return count;
}

Czy nie jest to tylko kwestia rozłożenia na czynniki liczby - określenia wszystkich czynników liczby? Następnie możesz zdecydować, czy potrzebujesz wszystkich kombinacji jednego lub więcej czynników.

Tak więc jeden możliwy algorytm to:

factor(N)
    divisor = first_prime
    list_of_factors = { 1 }
    while (N > 1)
        while (N % divisor == 0)
            add divisor to list_of_factors
            N /= divisor
        divisor = next_prime
    return list_of_factors

Następnie od Ciebie zależy połączenie czynników, aby określić pozostałą część odpowiedzi.

To jest coś, co wymyśliłem na podstawie odpowiedzi Justina. Może wymagać pewnej optymalizacji.

n=int(input())

a=[]
b=[]

def sieve(n):
    np = n + 1
    s = list(range(np)) 
    s[1] = 0
    sqrtn = int(n**0.5)
    for i in range(2, sqrtn + 1): 
        if s[i]:
            s[i*i: np: i] = [0] * len(range(i*i, np, i))
    return filter(None, s)

k=list(sieve(n))

for i in range(len(k)):
        if n%k[i]==0:
                a.append(k[i])

a.sort()

for i in range(len(a)):
        j=1
        while n%(a[i]**j)==0: 
                j=j+1
        b.append(j-1)

nod=1

for i in range(len(b)):
        nod=nod*(b[i]+1)

print('no.of divisors of {} = {}'.format(n,nod))

Myślę, że właśnie tego szukasz, robię dokładnie to, o co prosiłeś. Skopiuj i wklej go w Notatniku Zapisz jako * .bat.Run.Wprowadź numer.Proces pomnóż przez 2 i to jest liczba dzielników.Zrobiłem to celowo, aby szybciej określić dzielniki:

Pls pamiętać, że zmienna CMD obsługuje wartości powyżej 999999999

@echo off

modecon:cols=100 lines=100

:start
title Enter the Number to Determine 
cls
echo Determine a number as a product of 2 numbers
echo.
echo Ex1 : C = A * B
echo Ex2 : 8 = 4 * 2
echo.
echo Max Number length is 9
echo.
echo If there is only 1 proces done  it
echo means the number is a prime number
echo.
echo Prime numbers take time to determine
echo Number not prime are determined fast
echo.

set /p number=Enter Number : 
if %number% GTR 999999999 goto start

echo.
set proces=0
set mindet=0
set procent=0
set B=%Number%

:Determining

set /a mindet=%mindet%+1

if %mindet% GTR %B% goto Results

set /a solution=%number% %%% %mindet%

if %solution% NEQ 0 goto Determining
if %solution% EQU 0 set /a proces=%proces%+1

set /a B=%number% / %mindet%

set /a procent=%mindet%*100/%B%

if %procent% EQU 100 set procent=%procent:~0,3%
if %procent% LSS 100 set procent=%procent:~0,2%
if %procent% LSS 10 set procent=%procent:~0,1%

title Progress : %procent% %%%



if %solution% EQU 0 echo %proces%. %mindet% * %B% = %number%
goto Determining

:Results

title %proces% Results Found
echo.
@pause
goto start

myślę, że ten będzie poręczny i precyzyjny

script.pyton

>>>factors=[ x for x in range (1,n+1) if n%x==0] print len(factors)

Spróbuj czegoś w ten sposób:

int divisors(int myNum) {
    int limit = myNum;
    int divisorCount = 0;
    if (x == 1) 
        return 1;
    for (int i = 1; i < limit; ++i) {
        if (myNum % i == 0) {
            limit = myNum / i;
            if (limit != i)
                divisorCount++;
            divisorCount++;
        }
    }
    return divisorCount;
}

Nie znam NAJBARDZIEJ wydajnej metody, ale zrobiłbym co następuje:

• Utwórz tabelę liczb pierwszych, aby znaleźć wszystkie liczby pierwsze mniejsze lub równe pierwiastkowi kwadratowemu z danej liczby (Osobiście użyłbym Sito Atkina)
• Policz wszystkie liczby pierwsze mniejsze lub równe pierwiastkowi kwadratowemu z liczby i pomnóż to przez dwa. Jeśli pierwiastek kwadratowy liczby jest liczbą całkowitą, odejmij ją od zmiennej licznika.

Powinien działać \ o /

Jeśli potrzebujesz, mogę jutro zaprogramować coś w C, aby zademonstrować.