Algorytm obliczania liczby dzielników podanej liczby


177

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.


Biorąc pod uwagę Twoje wymagania, liczba czynników jest niejasna. Domyślam się, że szukasz liczby nieunikalnych dzielników pierwszych, ponieważ jeśli nie chcesz, aby kodowałem, po prostu napisz program, który zawsze zwraca 1, jeśli liczba do czynnika wynosi jeden, i 2, jeśli jest to cokolwiek innego. 0 może wymagać zmiany ...
Justin Bozonier

@sker: Czy istnieje zakres wartości, dla których potrzebujesz dzielników. Istnieje wiele sposobów obliczania współczynników, a każda metoda jest lepiej dopasowana do określonego zakresu.
Ande Turner

2
Oto powiązany interesujący problem projecteuler.net/problem=12
daniloquio

1
Naiwna Sito Atkina, nawet z edytowanego artykułu z Wikipedii, nigdy nie będzie szybsza niż Sito Eratostenesa z maksymalnym współczynnikiem koła, aż do ogromnych niepraktycznych ograniczeń, a wersje podzielone na segmenty są nawet bardziej na korzyść SoE (patrz SoE primesieve versus SoA primegen jako wdrożone przez partnera Atkina, Bernsteina. Powszechnie wiadomo w Internecie, że ich badanie dowiodło, że SoA jest szybsze, ale sztucznie ograniczyli optymalizację zastosowanego SoE, aby to udowodnić. Zobacz moją odpowiedź SoA po dalsze wyjaśnienia
GordonBGood

Odpowiedzi:


78

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.


1
Jeśli bierzesz pod uwagę dużą liczbę, nie chcesz nawet patrzeć na listę pierwszą. Chcesz jak najszybciej wyeliminować całe spektrum możliwości! Zobacz moją odpowiedź po więcej.
user11318

Zdaję sobie sprawę, że to było 2 lata temu, ale twoje łącze algo w Pythonie jest zepsute. Czy wiesz, gdzie teraz istnieje?
jb.

2
Taka n = (a^x * b^y * c^z)-(x + 1) * (y + 1) * (z + 1)jest zasada
SIslam

1
Jak mówi @Shashank, algorytm w sekcji „EDYCJA:” jest nieprawidłowy: Załóżmy, że n = 45 = 3 * 3 * 5. Największy dzielnik pierwszy to 5, ale pomnożenie go przez siebie, aż przekroczy n, spowoduje, że algorytm zgłosi, że ma 2 kopie współczynnika 5 (ponieważ 5 * 5 = 25 <45).
j_random_hacker

1
Sito Atkina ma w najlepszym przypadku złożoność środowiska wykonawczego O (N / log (log (N))) . Brute-force sprawdzanie wszystkich możliwych dzielników od 1 ... Sqrt (n) ma złożoność wykonania O (Sqrt (N)), która jest znacznie lepsza. Dlaczego ta odpowiedź została zaakceptowana?
le_m

47

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


1
Twoja technika jest bardzo sprytna, ale nie mówi mi, ile czynników ma ta liczba, prawda?
sker

23
Gdy masz już pierwszy rozkład na czynniki, obliczenie liczby czynników jest proste. Załóżmy, że czynniki pierwsze są p1, p2, ..., pk i są powtarzane razy m1, m2, ..., mk. Następnie mamy współczynniki (1 + m1) (1 + m2) ... (1 + mk).
user11318

Ciekawym sitem jest sito kwadratowe . Wykorzystuje teorię liczb - kongruencje kwadratowe i pewną algebrę liniową. Nauczyłem się wystarczająco dużo, aby używać go na drugim roku kursu teorii liczb na uniwersytecie.
Tanner

33

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

6
Czy (x% i) nie spowoduje dzielenia przez zero, gdy i = 0? czy powinienem = 1..limit?
rhu

@rhu Sprawdzanie 0 i tak jest bezcelowe, ponieważ 0 nie jest czynnikiem żadnej liczby.
EJoshuaS - Przywróć Monikę

29

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.


11

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

ale dlaczego zawsze zwiększasz liczbę o 2? ... czy jest jakieś twierdzenie, które zastosowałeś?
SummerCode

3
ponieważ walczysz tylko do sqrt (n). Na przykład: jeśli próbujesz znaleźć wszystkie dzielniki dla 36 - policzysz od 2 do 6. Wiesz, że 1 i 36,2 i 18, 3 i 12, 4 i 9, 6,6 są dzielnikami i występują w parach.
Antony Thomas

2
wielkie dzięki Anthony, teraz zrozumiałem: D! mały dodatek: myślę, że powinien traktować wartość sqrt (n) oddzielnie, ponieważ na razie bierze ją pod uwagę dwa razy zamiast jednego, myślę, że
SummerCode

O ile O (sqrt (n)) nie jest takie złe, nie jest optymalne. obliczenie rozkładu czynnika pierwszego może być wykonane znacznie szybciej i jest wystarczające do obliczenia liczby dzielników.
le_m

W każdej iteracji musisz obliczyć i², czy nie byłoby szybciej porównać i z √n (obliczone tylko raz)?
Yukulélé

10

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.


Tu jest link do jakiegoś pseudo kod na problem bardzo podobny do 2. answers.google.com/answers/threadview/id/392914.html
mR_fr0g

3
Pytanie nr 2 ma dobrze znane rozwiązanie. W przypadku rozkładania na czynniki {p_i, k_i}, gdzie p_ijest czynnikiem pierwszym liczby o k_ikrotności, całkowita liczba dzielników tej liczby wynosi (k_1+1)*(k_2+1)*...*(k_n+1). Myślę, że już to wiesz, ale zapisuję to na korzyść przypadkowego czytelnika.
Will Ness,

9

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.


6

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


5

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

5

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)

2
Chociaż ta funkcja zapewnia dekompozycję czynnika pierwszego n w rozsądnym czasie, jest a) nieoptymalna ib) nie oblicza liczby dzielników danej liczby zgodnie z pytaniem OP
le_m

I nie będzie działać dla dużych liczb ze względu na rekursję
whackamadoodle3000

Chociaż nie jest to optymalne i zamiast liczyć czynniki, w rzeczywistości je wymienia , prostota i piękno tego są niesamowite i dość szybkie. ^^
Gaurav Singhal

5

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


3

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.


3

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

2

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.


1
W pierwszej iteracji
miałbyś

Niestety nie. ++ i różni się od i ++ (co spowodowałoby błąd dzielenia przez zero)
iGbanam

Napisałem twoją funkcję w PHP i uruchomiłem ją - oto co mam - i.minus.com/iKzuSXesAkpbp.png
barfoon

z jakiegoś dziwnego powodu zadziałało to bez zarzutu. no cóż, moja wina. start numberOfDivisorsi iterator na 1; powinno to wyeliminować błąd dzielenia przez zero
iGbanam

1
Twój algorytm nie działa dla idealnych kwadratów. Na przykład zwraca 4 dla wejścia x = 4, ponieważ liczy 2 dwa razy ... 1, 2, 2, 4. Odpowiedź powinna być 3: 1,2,4
Michał

1

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


1
To da ci liczby pierwsze poniżej podanej liczby - ale nie ma gwarancji, że te liczby pierwsze będą dzielnikami? (chyba, że ​​czegoś mi brakuje)
Andrew Edgecombe

To szybki krok do znalezienia wszystkich liczb pierwszych <sqrt (N), które równo dzielą N.
SquareCog

1
Może to być szybki krok, ale testowanie wszystkich liczb pierwszych <sqrt (N) jest nadal złą techniką faktoryzacji, bez względu na to, jak skutecznie je znajdziesz. Jest wiele sposobów, aby to poprawić.
user11318

Testowanie liczb pierwszych to O (N), najtrudniejsza część to znalezienie liczb pierwszych. Ale nawet z niezoptymalizowanym sitem eratostenów nadal można znaleźć wszystkie liczby pierwsze poniżej kilku milionów w czasie poniżej sekundy. To obejmuje dowolną liczbę 64b i jestem pewien, że nie mówimy tutaj o faktorowaniu rzeczy na poziomie kryptograficznym
Matthew Scharley,

1

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  .

1

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

1

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++)
{
    ...
}

1

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

Nie wiem, co oblicza ta funkcja, ale na pewno nie jest to lista dzielników n.
le_m

1

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

    }
}

1

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

0

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.


0

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

0

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

882161280-1282 dzielniki
dondon

0

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)


0

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

-1

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


2
Jestem zmieszany. Zliczenie wszystkich liczb pierwszych mniejszych niż pierwiastek kwadratowy z liczby nie da ci jej dzielników ... nie każda liczba pierwsza mniejsza niż pierwiastek kwadratowy z danej liczby będzie dzielnikiem tej liczby.
Garrett Berg
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.