Как найти общее количество делителей до N? - PullRequest
Новая
       26

Как найти общее количество делителей до N?

1 голос
/ 06 сентября 2011

Учитывая число N, нужно найти число делителей для всех i, где i> = 1 и i <= N.Не могу понять. Должен ли я к этому, используя простую факторизацию?Предел N <= 10 ^ 9 Пример вывода: </p> 

1 --> 1
2 --> 3
3 --> 5
4 --> 8
5 --> 10
6 --> 14
7 --> 16
8 --> 20
9 --> 23
10 --> 27
11 --> 29
12 --> 35
13 --> 37
14 --> 41
15 --> 45

Ответы [ 3 ]

12 голосов
/ 16 июля 2013

Чтобы вычислить намного быстрее, используйте следующий псевдокод:

sum = 0; u = floor(sqrt(N)); foreach k <= u, sum += Floor(N / K); sum = 2*sum-u*u

Приведенная выше формула дана Питером Густавом Леженом Дирихле в 19 веке.

Я написал программу на C, используя вышеуказанный алгоритм, и на моем компьютере требуется 0,118 секунды для вычисления суммы числа делителей от 1 до 10 ^ 14. Ответ 3239062263181054.

2 голосов
/ 01 декабря 2011

, если вы хотите найти сумму всех делителей до заданного N, вам не нужен какой-либо факторинг. Вы можете сделать это (например) таким образом, с помощью уникального цикла. Начнем с 2, 2 - это делитель 2 * 2, 3 * 2, 4 * 2 и так далее. Это дает идею позади.

Foreach k

псевдокод:
sum = 0; foreach k <= N sum += Floor(N / K)

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

0 голосов
/ 06 сентября 2011

Не уверен, какой язык вы используете, но вот основная идея: 

dim myCount as integer = 1
dim N as integer = 10000000000 '10,000,000,000

For i as integer = 2 to N
   If N mod i = 0 Then
      myCount += 1
   End If
Next i

Примечания:

  • Мод дает вам остаток от деления.Так, например:
  • 10 mod 1 = 0 (потому что 1 входит в 10 10 раз точно)
  • 10 mod 2 = 0 (...
  • 10 mod 3= 1 (потому что 3 входит в 10 3 раза, с остатком 1)
  • 10 mod 4 = 2 (потому что 4 идет в 10 2 раза, с остатком 2)

Вы хотите считать только результаты, где N mod i = 0, потому что это единственные случаи, когда я перехожу к N без остатка, что Я думаю - это то, что ваш учитель, вероятно, имеет в виду, когда онискажем 'делитель' - без остатка.

Объявления переменных (dim ...) и цикл For могут быть написаны немного по-разному на любом языке, который вы используете. Код выше VB. Но если вызагляните в свой книжный указатель, вы, вероятно, найдете версию этих двух общих функций на вашем языке.

РЕДАКТИРОВАТЬ

ОК - в этом случае просто добавьте еще один FORпетля, следующим образом: 

dim myCount as integer = 1
dim N as integer = 10000000000 '10,000,000,000

For i as integer = 1 to N
   For j as integer = 2 to i
      If i mod j = 0 Then
         myCount += 1
      End If
   Next j
Next i
...