Вам нужно Сито Аткина, описанное здесь: http://en.wikipedia.org/wiki/Sieve_of_Atkin

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

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

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

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

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

Вот какой питон для алгоритмаСмотри сюда и ищите "Тема: математика - алгоритм нужны делители". Просто посчитайте количество элементов в списке, а не возвращайте их.

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

По сути, это сводится к тому, если ваш номер 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% в описании моего алгоритма, но если это не так, то это что-то похожее.

Я не знаю САМЫЙ эффективный метод, но я бы сделал следующее:

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

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

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

Сито Аткина - это оптимизированная версия сита Эратосфена, которое дает все простые числа до заданного целого. У вас должна быть возможность погуглить, чтобы получить более подробную информацию.

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

Основные шаги вычисления делителей для числа (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

Существует на много больше методов факторинга, чем решето Аткина. Например, предположим, что мы хотим разложить на множители 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. Я совершенно уверен, что он не выяснил это с помощью сита Аткина ...)

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

• общий обзор: http://en.wikipedia.org/wiki/Divisor_function

• значения для маленького n и некоторые полезные ссылки: A000005: d (n) (также называемый tau (n) или sigma_0 (n)), количество делителей n.

• реальный пример: факторизация целых чисел

Я не согласен с тем, что сито Аткина - это правильный путь, потому что проверка каждого числа в [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)

пс Это рабочий код Python для решения этой проблемы.

Этот интересный вопрос намного сложнее, чем кажется, и на него нет ответа. Этот вопрос можно разделить на 2 очень разных вопроса.

1 по N, найдите список L из N простых множителей

2 с учетом L, вычислить количество уникальных комбинаций

Все ответы, которые я вижу до сих пор, относятся к №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 имеет a 'дубликатов, а элемент b' имеет b 'дубликатов и т. д., Сколько уникальных комбинаций элементов от 1 до k-1 существует? Например, {2}, {2,2}, {2,2,2}, {2,3}, {2,2,3,3} каждое должно встречаться один раз и только один раз, если L = {2,2 , 2,3,3,5}. Каждая такая уникальная подгруппа является уникальным делителем N путем умножения элементов в подгруппе.

Вы можете попробовать это. Это немного взломано, но достаточно быстро.

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

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

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

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

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

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

Например: 36 Простое факторизация: 2 ^ 2 * 3 ^ 2 Делители: 1, 2, 3, 4, 6, 9, 12, 18, 36 Количество делителей: 9

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

Делители делают нечто впечатляющее: они полностью разделяются. Если вы хотите проверить количество делителей для числа n, очевидно, что это избыточно для охвата всего спектра, 1...n. Я не проводил глубоких исследований для этого, но решил Задача 12 проекта Эйлера о треугольных числах. Мое решение для теста больше 500 делителей длилось 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;
}

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

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

@Yasky

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

Пытаться:

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

ТОЛЬКО одна строка
Я очень тщательно обдумал ваш вопрос и попытался написать высокоэффективный и производительный фрагмент кода. Чтобы вывести на экран все делители заданного числа, нам понадобится всего одна строка кода! (используйте параметр -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;
}

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

здесь очень ясен метод простых чисел. 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  .

Вот простой алгоритм O (sqrt (n)). Я использовал это, чтобы решить Project 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

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

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

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

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

Ниже приведена программа на языке C для определения количества делителей заданного числа.

Сложность описанного выше алгоритма составляет 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++)
{
    ...
}

Вот функция, которую я написал. худшая временная сложность - 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;
}

Это эффективное решение:

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

Это самый простой способ вычисления делителей чисел:

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

    }
}

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

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

Я думаю, это то, что вы ищете. Я делаю именно то, о чем вы просили. Скопируйте и вставьте его в Блокнот. Сохраните как * .bat.Run. Введите число. Умножьте процесс на 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

@Kendall

Я протестировал ваш код и внес некоторые улучшения, теперь он стал еще быстрее. Я также тестировал код @ هومن جاویدپور, он также быстрее, чем его код.

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

я думаю, это будет удобно и точно

script.python

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

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

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