Algorithme pour trouver tous les diviseurs exacts d’un entier donné

Je veux trouver tous les diviseurs exacts d’un nombre. Actuellement j’ai ceci:

{ int n; int i=2; scanf("%d",&n); while(i<=n/2) { if(n%i==0) printf("%d,",i); i++; } getch(); } 

Y a-t-il un moyen de l’améliorer?

    Tout d’abord, votre code doit avoir la condition i <= n/2 , sinon il risque de rater l’un des facteurs. Par exemple, 6 ne sera pas imprimé si n = 12.

    Exécutez la boucle à la racine carrée du nombre (ie. i <= sqrt(n) ) et imprimez i et n/i (les deux seront des multiples de n).

     { int n; int i=2; scanf("%d",&n); while(i <= sqrt(n)) { if(n%i==0) { printf("%d,",i); if (i != (n / i)) { printf("%d,",n/i); } } i++; } getch(); } 

    Remarque :

    • Pour un carré parfait, afin que la racine carrée ne soit pas imprimée deux fois, la vérification supplémentaire est effectuée à la fin de la boucle pour i*i == n comme suggéré par @chepner.
    • Si vous souhaitez que tous les facteurs par ordre croissant stockent les valeurs dans un tableau, sortingez tous les nombres à la fin de la boucle et affichez-les.

    Trouver tous les diviseurs en utilisant “trouver tous les facteurs premiers” en C (plus rapide) et jusqu’à 18 chiffres.

     #include  #include  #include  #include  unsigned int FindDivisors(unsigned long long divisors[], unsigned long long N) { unsigned int lastdiv = 0; divisors[lastdiv++] = 1; unsigned long long powerfactor = 1; unsigned long long number = N; while ((number & 1) == 0) { powerfactor <<= 1; divisors[lastdiv++] = powerfactor; number >>= 1; } unsigned long long factor = 3; unsigned long long upto = lastdiv; powerfactor = 1; while (factor * factor <= number) { if (number % factor == 0) { powerfactor *= factor; for (unsigned int i = 0; i < upto; i++) divisors[lastdiv++] = divisors[i] * powerfactor; number /= factor; } else { factor += 2; upto = lastdiv; powerfactor = 1; } } if (number > 1) { if (number != factor) { upto = lastdiv; powerfactor = 1; } powerfactor *= number; for (unsigned int i = 0; i < upto; i++) divisors[lastdiv++] = divisors[i] * powerfactor; } return lastdiv; } int cmp(const void *a, const void *b) { if( *(long long*)a-*(long long*)b < 0 ) return -1; if( *(long long*)a-*(long long*)b > 0 ) return 1; return 0; } int main(int argc, char *argv[]) { unsigned long long N = 2; unsigned int Ndigit = 1; if (argc > 1) { N = strtoull(argv[1], NULL, 10); Ndigit = strlen(argv[1]); } unsigned int maxdiv[] = {1, 4, 12, 32, 64, 128, 240, 448, 768, 1344, 2304, 4032, 6720, 10752, 17280, 26880, 41472, 64512, 103680}; unsigned long long divisors[maxdiv[Ndigit]]; unsigned int size = FindDivisors(divisors, N); printf("Number of divisors = %u\n", size); qsort(divisors, size, sizeof(unsigned long long), cmp); for (unsigned int i = 0; i < size; i++) printf("%llu ", divisors[i]); printf("\n"); return 0; } 

    La recherche linéaire simple peut être améliorée en éliminant d’abord tous les facteurs de 2. Cela peut se faire par simple décalage de bits ou par comptage des zéros d’entraînement dotés d’une belle fonction insortingnsèque. C’est très rapide dans les deux cas. Exécutez ensuite l’algorithme suggéré par shg (qui fonctionnera beaucoup plus rapidement maintenant que les puissances de deux ne sont plus présentes) et combinez le résultat avec toutes les puissances possibles de deux (n’oubliez pas cette étape). Cela aide beaucoup pour les entrées qui ont beaucoup d’entrainement à zéro, mais ça marche même si elles ne le font pas – vous n’avez plus à tester les diviseurs même, donc la boucle est deux fois moins longue.

    Jeter des facteurs bas constants (mais supérieurs à 2) peut également aider. Le modulo avec une constante est presque certainement optimisé par le compilateur (ou sinon, vous pouvez le faire vous-même), mais surtout, cela signifie qu’il rest moins de diviseurs à tester. N’oubliez pas de combiner ce facteur avec les diviseurs que vous trouvez.

    Vous pouvez aussi factoriser complètement le nombre (utilisez votre algorithme préféré – le Rho de Pollard serait probablement le meilleur), puis imprimer tous les produits (à l’exception du produit vide et du produit complet) des facteurs. Cela a de bonnes chances d’être plus rapide pour les entrées plus volumineuses – l’algorithme Rho de Pollard trouve les facteurs très rapidement comparés à une simple recherche linéaire, il y a généralement moins de facteurs que les diviseurs appropriés, et la dernière étape (énumération des produits) implique uniquement des calculs rapides (pas de divisions). Cela aide principalement les nombres avec de très petits facteurs, ce que Rho trouve le plus rapide.

    Le code présenté dans l’une des réponses présente un bug difficile à voir au premier abord. Si sqrt (n) est un diviseur valide; mais n n’est pas un nombre carré parfait, deux résultats sont omis.

    Par exemple, essayez n = 15 et voyez ce qui se passe. sqrt(15) = 3 , la dernière valeur de la boucle while est donc 2. L’instruction suivante exécutée if (i * i == n) sera exécutée comme if(3 * 3 == 15) . Donc 3 n’est pas répertorié comme diviseur, 5 a également été oublié.

    Ce qui suit gérera correctement le cas général des entiers positifs.

      { int n; int i=2; scanf("%d",&n); while(i <= sqrt(n)) { if(n%i==0) { printf("%d,",i); if (i != (n / i)) { printf("%d,",n/i); } } i++; } getch(); } 
      int count = 2; //long childsum = 0; long _originalvalue = sum; dividend = "1"; for (int i = 2; i < sum; i++) { if (_originalvalue % i == 0) { sum = _originalvalue / i; //sum = childsum; dividend = dividend + "," + i+","+sum; if (sum == i) { count++; } else { count = count + 2; } } } return count; 

    Lorsque le nombre donné est impair, nous pouvons même ignorer les nombres pairs. Une légère improvisation dans le code accepté 🙂

    Voici le code Java pour rechercher les facteurs du nombre donné.

     import java.util.Scanner; public class Factors { public static void main(Ssortingng[] args) { Scanner scanner = new Scanner(System.in); int t=scanner.nextInt(); while(t-- > 0) { int n = scanner.nextInt(); if(n % 2 == 0) { for(int i = 1; i <= Math.sqrt(n); i++) { if(n % i == 0) { System.out.println(i + ", "); if(i != n/i) { System.out.println(n/i + ", "); } } } } else { for(int i = 1; i <= Math.sqrt(n); i=i+2) { if(n % i == 0) { System.out.println(i + ", "); if(i != n/i) { System.out.println(n/i + ", "); } } } } } } } 

    Ceci est ma nouvelle version C #. Merci à Rndm, il est presque 50 fois plus rapide que mon premier essai.

     public static long GetDivisors(long number) { long divisors = 0; long boundary = (long)Math.Sqrt(number); for (int i = 1; i <= boundary; i++) { if (number % i == 0) { divisors++; if(i != (number / i)) { if (i * i != number) { divisors++; } } } } return divisors; }