Алгоритм вычисления количества делителей заданного числа

Question

Какой будет наиболее оптимальный (с точки зрения производительности) алгоритм для вычисления числа делителей заданного числа?

Было бы замечательно, если бы вы предоставили псевдокод или ссылку на какой-нибудь пример.

РЕДАКТИРОВАТЬ: Все ответы были очень полезны, спасибо. Я внедряю «Сито Аткина», а затем я собираюсь использовать нечто похожее на то, что указал Джонатан Леффлер. Ссылка Джастина Бозонье содержит дополнительную информацию о том, что я хотел.

Answer 1

Учебники по теории чисел называют функцию подсчета делителей тау. Первый интересный факт заключается в том, что он мультипликативный, т.е. τ (ab) = τ (a) τ (b), когда a и b не имеют общего множителя. (Доказательство: каждая пара делителей a и b дает отдельный делитель ab).

Теперь обратите внимание, что для p простое число τ (p ** k) = k + 1 (степени p). Таким образом, вы можете легко вычислить τ (n) из его факторизации.

Однако факторизация больших чисел может быть медленной (безопасность криптографии RSA зависит от того, что произведение двух больших простых чисел трудно разложить). Это предполагает этот оптимизированный алгоритм

1. Проверка, является ли число простым (быстрым)
2. Если это так, вернуть 2
3. В противном случае, разложить число (медленно, если несколько больших простых множителей)
4. Вычислить τ (n) из факторизации

Answer 2

Вы можете предварительно вычислить простые числа до корня квадратного из максимально возможного N и вычислить показатель степени каждого простого множителя числа. Число делителей n (n = p1 ^ a p2 ^ b p3 ^ c ...) равно (a + 1) (b + 1) (c + 1), потому что оно такое же, как и способ объединения простых числа этого фактора (и это будет считать количество делителей). Это очень быстро, если вы предварительно вычислите простые числа

Более подробная информация об этом методе:

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

Answer 3

Попробуйте что-нибудь вроде этого:

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

Answer 4

Полагаю, этот будет удобен и точен

script.pyton

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

Answer 5

Я думаю, это то, что вы ищете. Я делаю именно то, что вы просили. Скопируйте и вставьте его в Блокнот. Сохраните как * .bat.Run.Enter Number. Умножьте процесс на 2, и это число делителей. Я специально сделал это, чтобы он быстрее определял делители:

Пожалуйста, обратите внимание, что переменная CMD не поддерживает значения более 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

Answer 6

Это то, что я придумал, основываясь на ответе Джастина. Это может потребовать некоторой оптимизации.

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

Answer 7

Я не знаю наиболее эффективного метода, но я бы сделал следующее:

• Создайте таблицу простых чисел, чтобы найти все простые числа, меньшие или равные квадратному корню из числа (лично я бы использовал Сито Аткина)
• Подсчитайте все простые числа, меньшие или равные квадратному корню из числа, и умножьте их на два. Если квадратный корень из числа является целым числом, то вычтите его из переменной count.

Должно работать \ o /

Если вам нужно, я могу написать кое-что завтра в C, чтобы продемонстрировать.

Answer 8

Разве это не просто вопрос факторизации числа - определения всех факторов числа? Затем вы можете решить, нужны ли вам все комбинации одного или нескольких факторов.

Итак, один из возможных алгоритмов будет:

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

Затем вы должны объединить факторы, чтобы определить остальную часть ответа.