Comment trouver le nombre total de N JUSQU'A diviseurs?

Question

Étant donné un nombre N, doivent trouver le numéro pour les diviseurs tous où i> = 1 et i <= N. Ne peut pas comprendre out.Do Je dois cela en utilisant factorisation? La limite est N <= 10 ^ 9 Sortie de l'échantillon:

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

Answer 1

Pour calculer beaucoup plus rapide, utilisez le pseudo-code suivant:

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

La formule ci-dessus est donnée par Peter Gustav Lejeune Dirichlet au 19ème siècle.

J'ai écrit un programme C en utilisant l'algorithme ci-dessus et il prend 0,118 secondes sur mon ordinateur à somme calcul du nombre de diviseurs de 1 jusqu'à 10 ^ 14. La réponse est 3239062263181054.

Answer 2

si vous voulez trouver la somme de tous les diviseurs jusqu'à un N donné, vous ne pas besoin d'affacturage. Vous pouvez le faire (par exemple) de cette façon, avec une boucle unique. Commencez avec 2, 2 est un diviseur de 2 * 2, 3 * 2, 4 * 2 et ainsi de suite. Cela donne à l'idée sous-jacente.

Foreach k

pseudocode:
sum = 0; foreach k <= N sum += Floor(N / K)

Notez que ce n'est pas la même chose comme demander le nombre de diviseurs d'un N donné.

Answer 3

Je ne sais pas quelle langue que vous utilisez, mais voici l'idée de base:

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

Notes:

• Mod vous donne le reste de la division. Ainsi, par exemple:
• 10 1 mod = 0 (car 1 va dans 10 10 fois exactement)
• 10 mod 2 = 0 (...
• 10 mod 3 = 1 (parce que 3 va en 10 3 fois, avec un reste de 1)
• 10 mod 4 = 2 (car 4 va dans 10 2 fois, avec une remainter de 2)

Vous voulez seulement compter les résultats N mod i = 0, car ce sont les seuls cas où je Goès en N sans reste; qui Je pense est ce que votre professeur signifie probablement quand ils disent « diviseur » -. sans reste

Les déclarations de variables (dim ...) et la boucle for peut être écrit de façon légèrement différente dans la langue que vous utilisez. Le code ci-dessus est VB. Mais si vous regardez dans l'index de livre, vous trouverez probablement votre version de langue de ces deux caractéristiques communes.

EDIT

OK - dans ce cas, il suffit d'ajouter une autre boucle FOR, comme suit:

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