il y a un lot plus de techniques de factorisation que le tamis D'Atkin. Par exemple, supposons que nous voulons facteur 5893. Sa racine est 76.76... Nous allons maintenant tenter d'écrire 5893 comme un produit de places. Eh bien (77*77 - 5893) = 36 qui est de 6 au carré, donc 5893 = 77*77 - 6*6 = (77 + 6)(77-6) = 83*71. Si ça n'avait pas marché, on aurait regardé si 78*78 - 5893 c'était un carré parfait. Et ainsi de suite. Avec cette technique, vous pouvez rapidement tester pour les facteurs près de la place racine de n beaucoup plus rapide qu'en testant des nombres premiers individuels. Si vous combinez cette technique pour écarter les grands nombres premiers avec un tamis, vous aurez une bien meilleure affacturage méthode qu'avec le tamis seul.

et ce n'est qu'une des nombreuses techniques qui ont été développées. C'est assez simple. Il vous faudrait beaucoup de temps pour apprendre, disons, assez de théorie des nombres pour comprendre les techniques de factoring basées sur des courbes elliptiques. (Je sais qu'ils existent. Je ne les comprends pas.)

donc à moins que vous ayez affaire à de petits entiers, je n'essaierais pas de résoudre ce problème moi-même. Au lieu de cela, j'essaierais de trouver un moyen d'utiliser quelque chose comme la bibliothèque PARI qui a déjà mis en œuvre une solution très efficace. Avec cela je peux factoriser un nombre aléatoire de 40 chiffres comme 1243213423321432131223434312213424231341 dans environ .05 secondes. (Sa factorisation, au cas où vous vous demandiez, est 29*439*1321*157907*284749*33843676813*4857795469949. Je suis convaincu qu'il n'a pas trouvé cela en utilisant le tamis D'Atkin...)

@Yasky

votre fonction diviseurs a un bug en ce qu'elle ne fonctionne pas correctement pour les carrés parfaits.

, Essayez:

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

Je ne suis pas d'accord que le tamis D'Atkin est la voie à suivre, parce qu'il pourrait facilement prendre plus de temps pour vérifier chaque nombre dans [1,n] pour la primalité que cela réduirait le nombre par divisions.

voici un code qui, bien que légèrement plus pirate, est généralement beaucoup plus rapide:

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 c'est du code python qui fonctionne pour résoudre ce problème.

cette question intéressante est beaucoup plus difficile qu'il n'y paraît, et il n'a pas été répondu. La question peut être divisée en deux questions très différentes.

1 donné N, trouver la liste L des facteurs principaux de N

2 donné L, calculer le nombre de combinaisons uniques

toutes les réponses que je vois jusqu'à présent se réfèrent à #1 et omettent de mentionner qu'il n'est pas tractable pour des nombres énormes. Pour les N de taille moyenne, même 64 bits, il est facile; pour l'énorme N, le problème de factoring peut prendre "pour toujours". Chiffrement à clé publique en dépend.

la Question 2 a besoin de plus de discussion. Si L ne contient que des nombres uniques, c'est un calcul simple en utilisant la formule de combinaison pour choisir des objets k de n articles. En fait, vous devez faire la somme des résultats de l'application de la formule tout en variant k de 1 à sizeof(L). Cependant, L contient généralement plusieurs occurrences de nombres premiers multiples. Par exemple, L = {2,2,2,3,3,5} est la factorisation de N = 360. Maintenant ce problème est assez difficile!

reformulation #2, étant donné que la collection c contient k articles, de sorte que l'article a a' duplicata, et l'article b A' duplicata, etc. combien de combinaisons uniques de 1 à k-1 les articles sont là? Par exemple:, {2}, {2,2}, {2,2,2}, {2,3}, {2,2,3,3} doit se produire une seule fois si L = {2,2,2,3,3,5}. Chacune de ces sous-collections est un diviseur unique de N en multipliant les articles de la sous-collection.

une réponse à votre question dépend grandement de la taille de l'entier. Les méthodes pour les petits nombres, par exemple moins de 100 bits, et pour les nombres ~1000 bits (tels que utilisés dans la cryptographie) sont complètement différents.

• aperçu général: http://en.wikipedia.org/wiki/Divisor_function

• valeurs " pour les petits n et quelques références utiles: AOOOOO5: d (n) (Aussi appelé tau(n) ou sigma_0 (n)), Le nombre de diviseurs de N.

• exemple du monde réel: factorisation d'entiers

voici un algorithme simple o(sqrt(n)). J'ai utilisé ceci pour résoudre projet 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
    count+=(1 if i**2==n else 0)
    return count  

une seule ligne

J'ai pensé très soigneusement à votre question et j'ai essayé d'écrire un code très efficace et performant Pour imprimer tous les diviseurs d'un nombre donné sur l'écran, nous avons besoin d'une seule ligne de code! (utiliser l'option-std=c99 lors de la compilation via 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

pour trouver des nombres de diviseurs, vous pouvez utiliser la fonction suivante très très rapide(fonctionne correctement pour tous les nombres entiers sauf 1 et 2)

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

ou si vous traitez un nombre donné comme un diviseur(travailler correctement pour tous les nombres entiers sauf 1 et 2)

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

NOTE:deux fonctions ci-dessus fonctionnent correctement pour tous les nombres entiers positifs sauf le nombre 1 et 2 donc, il est fonctionnel pour tous les nombres supérieurs à 2 mais si vous devez couvrir 1 et 2, Vous pouvez utiliser l'une des fonctions suivantes( un peu plus lentement)

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

ou

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

small is beautiful :)

le tamis D'Atkin est une version optimisée du tamis D'Eratosthène qui donne tous les nombres premiers jusqu'à un entier donné. Vous devriez être en mesure de google Cette pour plus de détails.

une fois que vous avez cette liste, il est simple de diviser votre nombre par chaque prime pour voir si c'est un diviseur exact (i.e., le reste est zéro).

les étapes de base calculant les diviseurs pour un nombre (n) sont [c'est le pseudocode converti du code réel ainsi I j'espère que je n'ai pas introduit d'erreurs]:

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

essayez celui-ci. C'est un peu hackish, mais c'est assez rapide.

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

une fois que vous avez le premier factorisation, il y a un moyen de trouver le nombre de diviseurs. Ajouter un à chacun des exposants sur chaque facteur individuel et ensuite multiplier les exposants ensemble.

par exemple: Trente six Première Factorisation: 2^2*3^2 Diviseurs: 1, 2, 3, 4, 6, 9, 12, 18, 36 Nombre de diviseurs: 9

Ajouter un à chaque exposant 2^3*3^3 Exposants multiples: 3*3 = 9

avant de vous engager à une solution, considérez que l'approche par tamis pourrait ne pas être une bonne réponse dans le cas typique.

il y a un moment, il y avait une question de prime et j'ai fait un test de temps--pour les entiers de 32 bits au moins déterminer si c'était prime était plus lent que la force brute. Il y a deux facteurs:

1) pendant qu'un humain prend un certain temps pour faire une division ils sont très rapides sur l'ordinateur--semblable au coût de chercher la réponse.

2) Si vous n'avez pas de table prime, vous pouvez faire une boucle qui tourne entièrement dans le cache L1. Cela le rend plus rapide.

C'est une solution efficace:

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

font quelque chose de spectaculaire: ils se divisent complètement. Si vous voulez vérifier le nombre de diviseurs d'un nombre, n , il est clairement inutile de couvrir l'ensemble du spectre, 1...n . Je n'ai pas fait de recherche en profondeur pour cela, mais j'ai résolu projet Euler problème 12 sur les nombres triangulaires . Ma solution pour le test plus grand que 500 diviseurs a fonctionné pendant 309504 microsecondes (~0,3 s). J'ai écrit cette fonction diviseur pour solution.

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

pour chaque algorithme, il y a un point faible. Je pensais que c'était faible contre des nombres premiers. Mais puisque les nombres triangulaires ne sont pas imprimés, il a servi son but sans faille. De mon profilage, je pense que ça a plutôt bien.

Joyeuses Fêtes.

vous voulez le tamis D'Atkin, décrit ici: http://en.wikipedia.org/wiki/Sieve_of_Atkin

la méthode du nombre premier est très claire ici . P [] est une liste de nombres premiers inférieur ou égal à la 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  .

théorie des nombres les manuels appellent la fonction de comptage de diviseurs tau. Le premier fait intéressant est qu'il est multiplicatif, c'est à dire. τ(ab) = τ(a)t(b) , si a et b n'ont aucun facteur commun. (Preuve: chaque paire de diviseurs de a et b donne un diviseur distinct de ab).

Maintenant, notez que pour p un nombre premier, τ(p**k) = k+1 (les puissances de p). Ainsi, vous pouvez facilement calculer τ(n) à partir de sa factorisation.

cependant la factorisation de grands nombres peut être lente (le la sécurité de la typographie RSA dépend du produit de deux grands nombres premiers difficiles à factoriser). Ce qui suggère cet algorithme optimisé

1. Test si le nombre est premier (fast)
2. si oui, retourner 2
3. sinon, factoriser le nombre (lent si plusieurs grands facteurs principaux)
4. calculer τ (n) à partir de la factorisation

est un programme C de trouver le nombre de diviseurs d'un nombre donné.

La complexité de l'algorithme ci-dessus est O(sqrt(n)).

cet algorithme fonctionnera correctement pour le nombre qui sont carrés parfaits ainsi que les nombres qui ne sont pas carrés parfaits.

notez que la limite supérieure de la boucle est définie à la racine carrée du nombre pour avoir l'algorithme le plus efficace.

Note que le stockage de la limite supérieure dans une variable séparée sauve aussi le temps, vous ne devriez pas appeler la fonction sqrt dans la section condition de la boucle for, cela sauve aussi votre temps de calcul.

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

au lieu de la boucle ci-dessus vous pouvez également utiliser la boucle suivante qui est encore plus efficace car cela supprime la nécessité de trouver la racine carrée du nombre.

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

Voici une fonction que j'ai écrite. sa plus grande complexité de temps est O(sqrt(n)),le meilleur temps d'autre part est O(log (n)). Il vous donne tous les diviseurs premiers avec le nombre de son occurrence.

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

C'est la façon la plus basique de calculer les diviseurs de nombre:

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

j'ai testé votre code et fait quelques améliorations, maintenant il est encore plus rapide. J'ai aussi testé avec le code de @هومن حاوستاية, c'est aussi plus rapide que son code.

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

n'est - ce pas simplement une question de factoriser le nombre-de déterminer tous les facteurs du nombre? Vous pouvez alors décider si vous avez besoin de toutes les combinaisons d'un ou de plusieurs facteurs.

donc, un algorithme possible serait:

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

C'est alors à vous de combiner les facteurs pour déterminer le reste de la réponse.

c'est quelque chose que J'ai inventé basé sur la réponse de Justin. Il pourrait exiger de l'optimisation.

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

je pense que c'est ce que vous cherchez.Je fais exactement ce que vous avez demandé. Copiez et collez-le dans le bloc-notes.Enregistrer sous *.chauve.Exécuter.Entrez Le Numéro.Multiplier le processus par 2 et c'est le nombre de diviseurs.Je l'ai fait exprès pour que l'it détermine plus rapidement les diviseurs:

Pls noter qu'un CMD varriable cant valeurs de prise en charge de plus de 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

je suppose que celui-ci sera pratique aussi bien que précis

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

Essayez quelque chose du genre:

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

vous pouvez précalculer des nombres premiers jusqu'à la racine carrée du maximum possible N et calculer l'exposant de chaque facteur premier d'un nombre. Le nombre de diviseurs de n (n = p1^p2^b p3^c...) est (a+1)(b+1) (c+1) parce que c'est la même chose que compter la façon de combiner les nombres premiers de ces facteurs (et cela comptera le nombre de diviseurs). C'est très rapide si vous précalculer les nombres premiers

informations plus détaillées sur cette méthode:

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

Je ne connais pas la méthode la plus efficace, mais je ferais ce qui suit:

• créer une table de nombres premiers pour trouver tous les nombres premiers inférieurs ou égaux à la racine carrée du nombre (personnellement, j'utiliserais le tamis D'Atkin)
• Compter tous les nombres premiers inférieurs ou égaux à la racine carrée du nombre et les multiplier par deux. Si la racine carrée du nombre est un entier, soustrayez un de la variable count.

Devrait fonctionner \o/

si vous avez besoin, je peux coder quelque chose demain en C.