Вопрос по algorithm, pseudocode, performance – Алгоритм вычисления количества делителей заданного числа

164

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

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

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

Вот связанная интересная проблемаprojecteuler.net/problem=12 daniloquio
@sker: Есть ли ряд значений, для которых вам нужны делители. Есть много способов расчета факторов, и каждый метод лучше подходит для определенного диапазона. Ande TURNER
Учитывая ваши требования, количество факторов является неопределенным. Я предполагаю, что вы ищете количество неуникальных простых делителей, потому что, если вы не хотите, чтобы я кодировал, просто напишите программу, которая всегда возвращает 1, если число к фактору равно единице, и 2, если это что-то еще. 0 может потребоваться изменение ... Justin Bozonier
Наивное «Сито Аткина», даже из отредактированной статьи Википедии, никогда не будет быстрее, чем «Сито Эратосфена» с максимальным факторизацией до огромных непрактичных пределов, а сегментированные на странице версии даже более благоприятны для SoE (см. Пример SoE против SoA primegen как реализованный партнером Аткина Бернштейном. Общеизвестно, что в Интернете неверно известно, что их исследование доказало SoA быстрее, но они искусственно ограничили оптимизацию SoE, используемую для доказательства этого.my SoA answer для дальнейшего объяснения GordonBGood

Ваш Ответ

28   ответов
0

script.pyton

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

47

lot больше техник факторинга, чем сита Аткина. Например, предположим, что мы хотим вычислить 5893. Ну, его sqrt равно 76,76 ... Теперь мы попробуем написать 5893 как произведение квадратов. Скважина (77 * 77 - 5893) = 36, то есть 6 в квадрате, поэтому 5893 = 77 * 77 - 6 * 6 = (77 + 6) (77-6) = 83 * 71. Если бы это не сработало, мы бы посмотрели, было ли 78 * 78 - 5893 идеальным квадратом. И так далее. С помощью этой техники вы можете быстро проверить факторы около квадратного корня из n гораздо быстрее, чем проверяя отдельные простые числа. Если вы объедините эту технику для исключения больших простых чисел с помощью сита, у вас будет намного лучший метод разложения, чем с одним ситом.

И это только одна из множества разработанных методик. Это довольно простой. Вам понадобится много времени, чтобы изучить, скажем, достаточно теории чисел, чтобы понять методы факторинга, основанные на эллиптических кривых. (Я знаю, что они существуют. Я их не понимаю.)

Поэтому, если вы не имеете дело с маленькими целыми числами, я не буду пытаться решить эту проблему самостоятельно. Вместо этого я попытаюсь найти способ использовать что-то вродеPARI библиотека, в которой уже реализовано высокоэффективное решение. При этом я могу вычислить случайное 40-значное число, например 124321342332143213122323434312213424231341, примерно за 0,05 секунды. (Его факторизация, если вам интересно, составляет 29 * 439 * 1321 * 157907 * 284749 * 33843676813 * 4857795469949. Я совершенно уверен, что это не удалось выяснить с помощью сита Аткина ...)

Интересное ситоquadratic sieve, Здесь используется теория чисел - квадратичные конгруэнции и некоторая линейная алгебра. Я выучил достаточно, чтобы использовать его на курсе теории чисел 2-го курса в университете.
Как только вы получите основную факторизацию, выяснить, сколько существует факторов, просто. Предположим, что первичными множителями являются p1, p2, ..., pk и они повторяются m1, m2, ..., mk раз. Тогда есть (1 + m1) (1 + m2) ... (1 + mk) факторов.
Вы техника очень умная, но она не говорит мне, сколько факторов имеет число, не так ли? sker
6

JUST one line
тивный и производительный фрагмент кода. Чтобы вывести на экран все делители заданного числа, нам понадобится всего одна строка кода! (используйте опцию -std = c99 при компиляции через 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

для нахождения чисел делителей вы можете использовать следующую очень очень быструю функцию (работает правильно для всех целых чисел, кроме 1 и 2)

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

или если вы рассматриваете данное число как делитель (работайте правильно для всех целых чисел, кроме 1 и 2)

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

ПРИМЕЧАНИЕ: две вышеуказанные функции работают правильно для всех положительных целых чисел, кроме чисел 1 и 2 так что это функционально для всех чисел, которые больше 2 но если вам нужно покрыть 1 и 2, вы можете использовать одну из следующих функций (немного медленнее)

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

ИЛИ ЖЕ

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

маленький красивый :)

8

проект эйлера

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  
Я тоже это видел ..
но почему вы всегда увеличиваете счет на 2? ... есть ли теорема, которую вы применили?
Неверно для n = 4.
спасибо большое Энтони, теперь я понял: D! небольшое дополнение: я думаю, что оно должно обрабатывать значение sqrt (n) отдельно, потому что сейчас оно учитывает два раза вместо одного, я думаю,
потому что вы используете только до sqrt (n). Например: если вы пытаетесь найти все делители для 36 - вы будете считать от 2 до 6. Вы знаете, что 1 и 36,2 и 18, 3 и 12, 4 и 9, 6,6 все делители, и они приходят в парах.
1

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

    }
}
27

что сито Аткина - это путь, потому что для проверки простоты каждого числа в [1, n] может потребоваться больше времени, чем для уменьшения числа делениями.

Вот некоторый код, который хотя и немного хакерский, но в целом гораздо быстрее:

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 Это рабочий код Python для решения этой проблемы.

9

небольших чисел, например менее 100 бит, а для чисел ~ 1000 бит (например, используемых в криптографии) совершенно разные.

general overview: http://en.wikipedia.org/wiki/Divisor_function

values for small n and some useful references: AOOOOO5: d(n) (also called tau(n) or sigma_0(n)), the number of divisors of n.

real-world example: factorization of integers

1

P [] - список простых чисел, меньших или равных 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

которую я написал. наихудшая временная сложность равна O (sqrt (n)), с другой стороны, наилучшее время - O (log (n)). Он дает вам все простые делители вместе с числом их появления.

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;
}
Я не знаю, что вычисляет эта функция, но это определенно не список делителей n.
1

ла.

Сложность вышеуказанного алгоритма составляет O (sqrt (n)).

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

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

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

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

Вместо приведенного выше цикла for вы также можете использовать следующий цикл, который является еще более эффективным, поскольку это устраняет необходимость в нахождении квадратного корня числа.

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

что вы хотите, чтобы «Сито Аткина» сформировало основной список, но я не верю, что это решает всю проблему. Теперь, когда у вас есть список простых чисел, вам необходимо увидеть, сколько из этих простых чисел действует как делитель (и как часто).

Вот немного Python для алгоритма Смотри сюда и найдите «Тема: математика - алгоритм делителей потребности». Просто посчитайте количество элементов в списке, а не возвращайте их.

Вот доктор Мат это объясняет, что именно нужно делать математически.

По сути это сводится к тому, если ваш номерn является:
n = a^x * b^y * c^z
(где a, b и c - простые делители n ', а x, y и z - количество повторений этого делителя) тогда общее количество для всех делителей будет:
(x + 1) * (y + 1) * (z + 1).

Редактировать: Кстати, чтобы найти a, b, c и т. Д., Вы захотите сделать то, что равносильно жадному алгоритму, если я правильно понимаю это. Начните с вашего наибольшего простого делителя и умножайте его до тех пор, пока дальнейшее умножение не превысит число n. Затем перейдите к следующему наименьшему коэффициенту и умножьте на предыдущее простое число ^ количество раз, которое он умножил на текущее простое число, и продолжайте умножать на простое число, пока следующее число не превысит n ... и т. Д. Следите за количеством раз, которое вы умножаете делители вместе и применить эти числа в формуле выше.

Не уверен на 100% в моем описании алгоритма, но если это не так, то это нечто подобное.

Алгоритм в «РЕДАКТИРОВАТЬ:» раздел неправильный ...
«Сито Аткина» имеет сложность во время выполненияO(N / log(log(N))) в лучшем случае. Проверка грубой силы всех возможных делителей из 1 ... Sqrt (n) имеет сложность во время выполненияO(Sqrt(N)) который намного выше. Почему этот ответ был принят?
Если вы учитываете большое число, вам даже не нужноlook в основном списке. Вы хотите максимально быстро исключить весь спектр возможностей! Смотрите мой ответ для более.
Как говорит @Shashank, алгоритм в «РЕДАКТИРОВАТЬ:» раздел неправильный: предположим, что n = 45 = 3 * 3 * 5. Наибольший простой делитель равен 5, но умножение его на единицу до тех пор, пока оно не превысит n, заставит алгоритм сообщить, что у него есть 2 копии фактора 5 (поскольку 5 * 5 = 25 & lt; 45).
Такn = (a^x * b^y * c^z)-(x + 1) * (y + 1) * (z + 1) это правило
10

чем кажется, и на него нет ответа. Вопрос можно разбить на 2 очень разных вопроса.

1 given N, find the list L of N's prime factors 2 given L, calculate number of unique combinations

Все ответы, которые я вижу до сих пор, относятся к № 1 и не в состоянии упомянуть, что он не поддается огромным количествам. Для N среднего размера, даже для 64-битных чисел, это легко; для огромного N проблема факторинга может занять «навсегда». Шифрование с открытым ключом зависит от этого.

Вопрос № 2 требует дальнейшего обсуждения. Если L содержит только уникальные числа, это простой расчет с использованием формулы комбинации для выбора k объектов из n элементов. На самом деле, вам нужно суммировать результаты применения формулы при изменении k от 1 до sizeof (L). Однако L обычно будет содержать несколько вхождений нескольких простых чисел. Например, L = {2,2,2,3,3,5} является факторизацией N = 360. Теперь эта проблема довольно сложная!

Возвращаясь к # 2, данная коллекция C содержит k элементов, так что элемент a имеет & apos; дубликаты, а пункт b имеет b & a; дубликаты и т. д. Сколько существует уникальных комбинаций от 1 до k-1 предметов? Например, {2}, {2,2}, {2,2,2}, {2,3}, {2,2,3,3} должны появляться каждый раз и только один раз, если L = {2,2 , 2,3,3,5}. Каждая такая уникальная подгруппа является уникальным делителем N путем умножения элементов в подгруппе.

Вопрос № 2 имеет хорошо известное решение. Для факторизации {p_i, k_i} гдеp_i является основным фактором числа сk_i кратность, общее число делителей этого числа(k_1+1)*(k_2+1)*...*(k_n+1), Я думаю, вы уже знаете это, но я запишу это для пользы, если случайный читатель здесь.
Вот ссылка на некоторый псевдокод для задачи, очень похожей на 2.answers.google.com/answers/threadview/id/392914.html
1

Я проверил ваш код и сделал некоторые улучшения, теперь он стал еще быстрее. Я также тестировал с @ & # x647; & # x648; & # x645; & # x646; & # X62C; & # x627; & # x648; & # x6CC; & # x62F; & # x67E; & # x648; & # x631; код, это также быстрее, чем его код.

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

они делятся полностью. Если вы хотите проверить количество делителей для числа,nэто явно избыточно, чтобы охватить весь спектр,1...n, Я не провел каких-либо углубленных исследований для этого, но я решилЗадача проекта Эйлера 12 о треугольных числах, Мое решение дляgreater then 500 divisors Тест проходил в течение 309504 микросекунд (~ 0,3 с). Я написал эту функцию делителя для решения.

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

У каждого алгоритма есть слабое место. Я думал, что это было слабым против простых чисел. Но так как треугольные числа не напечатаны, это послужило своей цели безупречно. Из моего профилирования я думаю, что все прошло хорошо.

Счастливых праздников.

Я написал вашу функцию на PHP и запустил ее - вот что я получил -i.minus.com/iKzuSXesAkpbp.png
по какой-то странной причине, это сработало для меня безупречно. да ладно, мой плохой. НачнитеnumberOfDivisors и итератор в 1; это должно избавить от деления на ноль ошибок
У вас есть деление на 0 на первой итерации здесь
Ваш алгоритм не работает для идеальных квадратов. Например, он возвращает 4 для входа x = 4, потому что он считает 2 дважды ... 1, 2, 2, 4. Ответ должен быть 3: 1,2,4
к сожалению нет. ++ i отличается от i ++ (что приведет к ошибке деления на ноль)
5

которая дает все простые числа до заданного целого числа. Вы должны быть в состоянии Google это для более подробной информации.

Как только у вас есть этот список, просто делить ваше число на каждое простое число, чтобы увидеть, является ли он точным делителем (то есть остаток равен нулю).

Основные этапы вычисления делителей для числа (n): [это псевдокод, преобразованный из реального кода, поэтому я надеюсь, что я не внес ошибок]:

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
33

Ваша функция делителей имеет ошибку в том, что она не работает правильно для идеальных квадратов.

Пытаться:

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;
}
Вы не должны продолжать после того, как я больше, чем sqrt (x) ...
Разве t (x% i) вызывает деление на ноль, когда i = 0? должен ли я = 1..limit?
@rhu Проверять 0 в любом случае бессмысленно, потому что 0 не является фактором любого числа.
0

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

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

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

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

0

корня максимально возможного 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;
    }
}
0

Скопируйте и вставьте его в Блокнот. Сохраните как * .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
882161280 - 1282 divisors – dondon Feb 7 '16 at 22:49
1

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

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

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

Test if the number is prime (fast) If so, return 2 Otherwise, factorise the number (slow if multiple large prime factors) Compute τ(n) from the factorisation
0

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

def factors(n):
    for x in xrange(2,n):
        if n%x == 0:
            return (x,) + factors(n/x)
    return (n,1)
Хотя эта функция обеспечивает разложение по главному коэффициенту n за разумное время, она а) не оптимальна и б) не вычисляет количество делителей данного числа в соответствии с вопросом OP.
И не будет работать на большие числа из-за его рекурсии
Хотя это не оптимально, а скорееcounting факторы, это на самом делеlists их, простота и красота этого удивительны и достаточно быстры. ^^
3

что подход Sieve может не быть хорошим ответом в типичном случае.

Некоторое время назад возник главный вопрос, и я провел временный тест - по крайней мере, для 32-разрядных целых чисел определялось, было ли оно простым, медленнее, чем грубая сила. Существует два фактора:

1) В то время как человеку требуется некоторое время, чтобы выполнить деление, он очень быстро работает на компьютере - похоже на стоимость поиска ответа.

2) Если у вас нет основной таблицы, вы можете создать цикл, который полностью выполняется в кеше L1. Это делает это быстрее.

-1

Create a table of primes to find all primes less than or equal to the square root of the number (Personally, I'd use the Sieve of Atkin) Count all primes less than or equal to the square root of the number and multiply that by two. If the square root of the number is an integer, then subtract one from the count variable.

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

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

Я в замешательстве. Подсчет всех простых чисел, меньших квадратного корня из числа, не даст вам его делителей ... не каждое простое число, меньшее квадратного корня из числа, будет делителем для этого числа.
0

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

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))
1
Тестирование простых чисел - это O (N), оно находит простые числа, которые являются трудной частью. Но даже с неоптимизированным ситом из эратосфена вы можете найти все простые числа менее нескольких миллионов за секунду. Это относится к любому числу 64b, и я уверен, что мы не говорим о факторинге криптоуровня.
Отсюда можно быстро перейти к поиску всех простых чисел & lt; sqrt (N), которые равномерно делят N.
Это даст вам простые числа ниже заданного вами числа, но нет ли гарантии, что эти простые числа будут делителями? (если я что-то упустил)
Это может быть быстрый скачок, но тестирование всех простых чисел & lt; sqrt (N) - все еще плохая техника факторинга, независимо от того, насколько эффективно вы их найдете. Есть много способов улучшить это.
3

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

есть способ найти число делителей. Добавьте один к каждому из показателей в каждом отдельном факторе и затем умножьте показатели вместе.

For example: 36 Prime Factorization: 2^2*3^2 Divisors: 1, 2, 3, 4, 6, 9, 12, 18, 36 Number of Divisors: 9

Добавьте один к каждому показателю степени 2 ^ 3 * 3 ^ 3 Умножьте показатели: 3 * 3 = 9

Похожие вопросы