it-swarm-eu.dev

Algoritmus pro výpočet počtu dělitelů daného čísla

Jaký by byl nejoptimálnější algoritmus (výkonnostní) pro výpočet počtu dělitelů daného čísla?

Bude to skvělé, pokud byste mohli poskytnout pseudokód nebo odkaz na nějaký příklad.

EDIT: Všechny odpovědi byly velmi užitečné, děkuji. Realizuji síto Atkina a pak použiji něco podobného, ​​co naznačil Jonathan Leffler. Odkaz, který napsal Justin Bozonier, má další informace o tom, co jsem chtěl.

164
sker

Dmitriy má pravdu, že budete chtít, aby Sieve of Atkin vytvořil prvotřídní seznam, ale nevěřím, že se o celý problém postará. Nyní, když máte seznam prvočísel, budete muset zjistit, kolik z těchto prvočísel funguje jako dělitel (a jak často).

Zde je několik pythonů pro algo Podívejte se zde a hledejte "Předmět: matematický algoritmus - potřebujete dělící algoritmus". Namísto jejich vrácení však spočítejte pouze počet položek v seznamu.

Zde je Dr. Math která vysvětluje, co přesně potřebujete udělat matematicky.

V podstatě se sníží, pokud je vaše číslo n:
n = a^x * b^y * c^z
(kde a, b, a c jsou n hlavní dělitele a x, y a z jsou počet opakování tohoto dělitele) pak celkový počet všech dělitelů je:
(x + 1) * (y + 1) * (z + 1).

Edit: BTW, najít a, b, c, atd. Budete chtít dělat to, co se rovná chamtivému algo, pokud to chápu správně. Začněte s Vaším největším prvočíselným dělitelem a vynásobte jej sám, dokud další násobení nepřekročí číslo n. Pak se přesuňte na další nejnižší faktor a časy dřívějšího prvočísla, kolikrát byl násoben současným prvočíslem a vynásobte prvočíslem, dokud další překročí n ... atd. Sledujte, kolikrát jste násobili dělit dohromady a uplatnit tato čísla do výše uvedeného vzorce.

Ne 100% jistý o mém algo popisu, ale pokud to není to něco podobného.

76
Justin Bozonier

@ Yasky

Funkce dělitele má chybu v tom, že nepracuje správně pro dokonalé čtverce.

Snaž se:

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

Nesouhlasím s tím, že síto Atkin je cesta, protože to by mohlo snadno trvat déle kontrolovat každé číslo v [1, n] pro primality, než by bylo snížení počtu divizí.

Zde je nějaký kód, který, i když je trochu hacker, je obecně mnohem rychlejší:

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 funguje python kód vyřešit tento problém.

27
Tyler

Tato zajímavá otázka je mnohem těžší, než vypadá, a nebyla zodpovězena. Otázka může být zohledněna ve dvou velmi odlišných otázkách.

1 dali N, najděte seznam L primárních faktorů N

2 dejte L, spočítejte počet unikátních kombinací

Všechny odpovědi, které vidím doposud, se vztahují k # 1 a nezmiňují se o tom, že to není možné pro enormní čísla. Pro středně velká, dokonce 64bitová čísla je to snadné; pro enormní N může faktoringový problém trvat "navždy". Šifrování veřejného klíče závisí na tom.

Otázka č. 2 potřebuje více diskuse. Pokud L obsahuje pouze jedinečná čísla, jedná se o jednoduchý výpočet pomocí kombinačního vzorce pro výběr k objektů z n položek. Ve skutečnosti je třeba shrnout výsledky z použití vzorce při proměnné k od 1 do sizeof (L). L však obvykle obsahuje více výskytů více prvočísel. Například, L = {2,2,2,3,3,5} je faktorizace N = 360. Nyní je tento problém poměrně obtížný! 

Přepočítání # 2, dané kolekce C obsahující k položky, taková položka a má 'duplikáty, a položka b má duplikáty b, atd., Kolik jedinečných kombinací položek 1 až k-1 existuje? Například {2}, {2,2}, {2,2,2}, {2,3}, {2,2,3,3} se musí vyskytnout jednou a pouze jednou, pokud L = {2,2 , 2,3,3,5}. Každý takový jedinečný dílčí soubor je jedinečný dělitel N vynásobením položek v dílčí sbírce.

10
dongilmore

Odpověď na vaši otázku závisí do značné míry na velikosti celého čísla. Způsoby pro malá čísla, např. méně než 100 bitů a pro čísla ~ 1000 bitů (například v kryptografii) jsou zcela odlišné.

9
jfs

Zde je rovný algoritmus O(sqrt(n)). Použil jsem to k vyřešení 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
    count+=(1 if i**2==n else 0)
    return count  
8
Antony Thomas

JUST jeden řádek
Myslel jsem velmi opatrně na vaši otázku a snažil jsem se napsat velmi efektivní a výkonný kus kódu Pro tisk všech dělitelů daného čísla na obrazovce potřebujeme jen jeden řádek kódu! (při kompilaci pomocí gcc použijte volbu -std = c99)

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

pro zjištění počtu dělitelů můžete použít následující velmi velmi rychlou funkci (pracovat správně pro celé číslo kromě 1 a 2)

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

nebo pokud s daným číslem zachází jako s dělitelem (pracuje správně pro celé číslo kromě 1 a 2) 

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

POZNÁMKA: dvě výše uvedené funkce pracují správně pro všechna kladná čísla s výjimkou čísla 1 a 2 , Takže je funkční pro všechna čísla, která jsou větší než 2 , Ale pokud potřebujete zahrnout 1 a 2, použít jednu z následujících funkcí (o něco pomalejší)

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

OR

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

malý je krásný :)

Můžete to zkusit. Je to trochu hackish, ale je to poměrně rychlé.

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

Sít Atkin je optimalizovaná verze síta Eratosthenes který dá všechna prvočísla nahoru k danému celému číslu. Měli byste být schopni google to pro více informací.

Jakmile budete mít tento seznam, je to jednoduchá záležitost rozdělit vaše číslo každým prvočíslem, abyste zjistili, zda je to přesný dělitel (tj. Zbytek je nula).

Základní kroky výpočtu dělitelů pro číslo (n) jsou [to je pseudocode převeden z reálného kódu, takže doufám, že jsem nezavedl chyby]:

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
paxdiablo

Jakmile máte primární faktorizaci, existuje způsob, jak zjistit počet dělitelů. Přidejte jeden do každého exponentu na každý jednotlivý faktor a pak násobte exponenty dohromady.

Například: 36 Prime Factorization: 2 ^ 2 * 3 ^ 2 Oddělovače: 1, 2, 3, 4, 6, 9, 12, 18, 36 Počet dělitelů: 9

Přidejte jeden ke každému exponentu 2 ^ 3 * 3 ^ 3 Vynásobte exponenty: 3 * 3 = 9

5
D. Williams

Než se dopustíte řešení, domnívejte se, že přístup Sieve nemusí být v typickém případě dobrou odpovědí.

Zatímco tam byla hlavní otázka a já jsem udělal časový test - pro 32-bitová celá čísla přinejmenším určení, zda to bylo prvočíslo, bylo pomalejší než hrubá síla. Existují dva faktory:

1) Zatímco člověk trvá nějakou dobu, než udělá divizi, je v počítači velmi rychlý - podobně jako náklady na vyhledávání odpovědi.

2) Pokud nemáte primární tabulku, můžete vytvořit smyčku, která běží zcela v mezipaměti L1. To zrychluje.

3
Loren Pechtel

Toto je efektivní řešení:

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

Dělníci dělají něco velkolepého: úplně se dělí. Chcete-li zkontrolovat počet dělitelů pro číslo, n, je jasné, že je zbytečné překlenout celé spektrum, 1...n. Neprovedl jsem pro to žádný hloubkový výzkum, ale vyřešil jsem Projekt Eulerův problém 12 na trojúhelníkových číslech . Moje řešení testu větší než 500 dělitelů trvalo 309504 mikrosekund (~ 0,3 s). Tuto dělitelskou funkci jsem napsal pro řešení.

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

Ke každému algoritmu existuje slabá stránka. Myslel jsem, že to je slabé proti prvočíslům. Ale protože trojúhelníková čísla nejsou tisknuta, bezchybně sloužila svému účelu. Z mého profilování si myslím, že to bylo docela dobře.

Šťastné svátky.

2
iGbanam

Chcete Sieve of Atkin, popsané zde: http://en.wikipedia.org/wiki/Sieve_of_Atkin

1
SquareCog

@Kendall

Testoval jsem váš kód a udělal několik vylepšení, nyní je to ještě rychlejší. Také jsem testoval s kódem @ مومن جاویدپور, což je také rychlejší než jeho kód.

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;
}
1
Abhishek Agrawal

Zde je funkce, kterou jsem napsal. je to nejhorší časová složitost je O (sqrt (n)), nejlepší čas na druhé straně je O (log (n)). To vám dává všechny hlavní dělitele spolu s počtem jeho výskytu.

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;
}
1
Adilli Adil

Následuje program C pro zjištění počtu dělitelů daného čísla.

Komplexnost výše uvedeného algoritmu je O (sqrt (n)).

Tento algoritmus bude pracovat správně pro číslo, které je perfektní čtverec, stejně jako čísla, která nejsou dokonalým čtvercem.

Všimněte si, že horní limit smyčky je nastaven na druhou mocninu čísla, aby algoritmus byl nejefektivnější.

Všimněte si, že uložení upperlimit v samostatné proměnné také šetří čas, neměli byste volat funkci sqrt v sekci podmínky smyčky for, což také šetří výpočetní čas.

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

Namísto výše uvedené smyčky můžete také použít následující smyčku, která je ještě efektivnější, protože to odstraňuje potřebu najít druhou odmocninu čísla.

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

Toto je nejzákladnější způsob výpočtu počtu dělitelů:

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
Malik

Učebnice teorie čísel volají funkci dělitele počítání tau. První zajímavou skutečností je, že je multiplikativní, tzn. τ (ab) = τ (a) τ (b), když a a b nemají společný faktor. (Důkaz: každý pár dělitelů a a b dává zřetelný dělitel ab).

Všimněte si, že pro p a prime, τ (p ** k) = k + 1 (pravomoci p). Můžete tak snadno vypočítat τ (n) z jeho faktorizace. 

Faktorizace velkých počtů však může být pomalá (bezpečnost kryogenní RSA závisí na produktu dvou velkých přípravků, které je těžké faktorizovat). To naznačuje tento optimalizovaný algoritmus

  1. Test, zda je číslo prvočíslo (rychlé)
  2. Pokud ano, vraťte se zpět 2
  3. V opačném případě faktorizujte číslo (pomalé, pokud je více velkých prvočísel)
  4. Vypočtěte τ (n) z faktorizace
1
Colonel Panic

metoda primárního čísla je zde velmi jasná. P [] je seznam prvočísel menší než nebo rovno 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
abdelkarim

Není to jen otázka faktoringu čísla - určování všech faktorů čísla? Pak se můžete rozhodnout, zda potřebujete všechny kombinace jednoho nebo více faktorů.

Jeden možný algoritmus by tedy byl:

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

Je pak na vás, abyste zkombinovali faktory, abyste určili zbytek odpovědi.

0
Jonathan Leffler

To je něco, co jsem přišel na základě Justinovy ​​odpovědi. To může vyžadovat určitou optimalizaci.

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
winsid96

Můžete předkompilovat předvolby až do kořene sqaure maximálního možného N a vypočítat exponent každého primárního faktoru čísla. Počet dělitelů n (n = p1 ^ a p2 ^ b p3 ^ c ...) je (a + 1) (b + 1) (c + 1), protože je stejný jako počet způsobů kombinování prvočísla počet těchto faktorů (a to bude počítat počet dělitelů). Je to velmi rychlé, pokud předkompenzujete prvočísla

Podrobnější informace o této metodě:

https://mathschallenge.net/library/number/number_of_divisors

https://www.math.upenn.edu/~deturck/m170/wk2/numdivisors.html

http://primes.utm.edu/glossary/xpage/tau.html

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

int divisors_count(const vector<int>& primes, int n)
{
    int divisors = 1;
    for (int i = 0; i < primes.size(); ++i) {
        int factor = primes[i];
        int factor_exponent = 0;
        while (n % factor == 0) {
            ++factor_exponent;
            n /= factor;
        }
        divisors *= (factor_exponent + 1);
    }
    if (n > 1) 
        return 2*divisors; // prime factor > sqrt(MAX_N)
    return divisors;
}

int main()
{
    const int MAX_N = 1e6;
    int max_factor = sqrt(MAX_N);

    vector<char> prime(max_factor + 1, true);
    for (int i = 3; i <= max_factor; i += 2) {
        if (prime[i]) {
            for (int j = 3*i; j <= max_factor; j += 2*i) {
                prime[j] = false;
            }   
        }
    }

    vector<int> primes;
    primes.reserve(max_factor/2);
    primes.Push_back(2);
    for (int i = 3; i <= max_factor; i += 2) {
        if (prime[i]) {
            primes.Push_back(i);
        }
    }

    int n;
    while (cin >> n) {
        cout << divisors_count(primes, n) << endl;
    }
}
0
izanbf1803

Zkuste něco podle těchto pokynů:

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;
}
0
Bryant Jackson

Myslím, že to je to, co hledáte for.I dělá přesně to, co jste požádali o. Kopírovat a vložit jej do programu Poznámkový blok.Save jako *. rozdělovačů. Udělal jsem to záměrně, aby určil dělitele rychleji:

Pls na vědomí, že CMD pestré převýšení podporuje hodnoty nad 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
0
dondon