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

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

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

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

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

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

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

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

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

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

повторение #2, учитывая коллекцию C, содержащую k элементов, так что элемент 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 путем умножения элементов в подколлекции.

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

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

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

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

вот прямой алгоритм O(sqrt(n)). Я использовал это, чтобы решить проект Эйлера

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  

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

мал, да удал :)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

делители делают что-то захватывающее: они делят полностью. Если вы хотите проверить количество делителей для числа 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;
}

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

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

вы хотите сито Аткина, описанное здесь:http://en.wikipedia.org/wiki/Sieve_of_Atkin

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

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

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

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

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

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

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

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

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

обратите внимание, что хранение upperlimit в отдельном переменная также экономит время, вы не должны вызывать функцию 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;
}

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

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

    }
}

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

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

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

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

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

Pls обратите внимание, что CMD varriable cant поддерживает значения более 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

Я думаю, что это будет удобно, а также точно

сценарий.pyton

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

вы можете предварительно вычислить простые числа до квадратного корня из максимально возможного N и вычислить показатель степени каждого простого множителя числа. Количество делителей N (где N = Р1^Р2^Р3 б^с...) является (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;
    }
}

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

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

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

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