Algorithme pour trouver tous exactement les diviseurs d'un nombre entier donné

Je veux trouver tous exactement les diviseurs 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();
}

Est-il un moyen de l'améliorer?

InformationsquelleAutor jairaj | 2012-07-28

55

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

Exécuter la boucle à la racine carrée du nombre (ie. i <= sqrt(n)) et l'impression à la fois 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, de sorte que la racine carrée n'est pas imprimé deux fois, la vérification supplémentaire est fait à la fin de la boucle pour i*i == n comme suggéré par @chepner.
- Si vous souhaitez que tous les facteurs dans l'ordre croissant de stocker les valeurs dans un tableau puis à la fin de la boucle de sorte que tous les chiffres et l'affichage.
- vous pouvez modifier printf("%d,", i);printf("%d,", n/i); à printf("%d,", i); if(i != n/i){printf("%d,", n/i);}.Pour un carré parfait, il ne sera pas imprimé deux fois de la racine.
- Ajouté dans le code.
- Vous pouvez éviter les multiples contrôles pour n/i !=i par itération sur i < sqrt(n), ce qui implique que n/i != i, puis de vérifier i=sqrt(n) en dehors de la boucle while comme un seul cas de bord.
- Grande pensée , mon mal de ne pas s'en rendre compte. Vais l'ajouter, merci.
- ce qui est la preuve que tous les diviseurs pourrait être trouvé en effectuant une boucle à sqrt(n) fois ? veuillez expliquer.
- il semble que votre idée ne fonctionnera pas sur n=8.
- Comment ? Il permet d'imprimer 2 et 4. Faites-vous allusion au fait que 1 et 8 ne sera pas imprimé ?
- prendre i=1 au lieu de i=2
- notez que i <= sqrt(n) promeut j'ai en double. Vous pouvez utiliser i <= (int)sqrt(n) pour éviter cela. Il serait plus rapide de changer if (i != (n / i)) à if (i*i != n) .
InformationsquelleAutor Rndm

Trouver tous les diviseurs en utilisant la fonction "recherche de tous les facteurs premiers" dans C (plus rapide)
et jusqu'à 18 chiffres.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
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;
}

InformationsquelleAutor ManAndPC

2

La simple recherche linéaire peut être améliorée en premier à jeter tous les facteurs de 2. Qui peut être fait par simple décalage de bits, ou le comte de formation de zéro avec une belle fonction intrinsèque. C'est très rapide dans les deux cas. Ensuite, exécutez l'algorithme proposé par shg (qui s'exécute beaucoup plus rapidement maintenant que les puissances de deux ne sont pas présents), et de combiner les résultats avec toutes les puissances de deux (n'oubliez pas cette étape). Cela aide beaucoup pour les entrées qui ont beaucoup de formation de zéro, mais il aide même si ils ne le font pas, vous ne pas avoir à tester des diviseurs de plus, afin que la boucle devient la moitié du temps.

Jeter quelques constante des facteurs (mais plus grand que 2) peut également aider. Modulo une constante est presque certainement optimisé par le compilateur (ou si pas, vous pouvez le faire vous-même), mais plus important encore, cela signifie qu'il ya moins de diviseurs de la gauche à l'épreuve. N'oubliez pas de combiner ce facteur avec les diviseurs vous trouvez.

Vous pouvez également factoriser le nombre complètement (utilisez votre favori algorithme probablement Pollard Rho serait le mieux), puis l'imprimer tous les produits (sauf le vide et le plein de produits) des facteurs. Cela a une bonne chance de se retrouver en étant plus rapide pour les plus grosses entrées - Pollard Rho algorithme recherche des facteurs très rapidement par rapport à une simple recherche linéaire, il y a généralement moins de facteurs de diviseurs propres, et la dernière étape (l'énumération des produits) n'implique rapide des mathématiques (pas de divisions). La plupart du temps cela aide pour les nombres avec de petits facteurs qui Rho le plus rapide.
- u pourrait donner un exemple de comment faire pour supprimer tous les facteurs de 2 par le décalage de bits.Les opérations sur les bits sont plus rapides ainsi que serait certainement améliorer les performances.
- dire que vous prenez 24, la racine carrée est près de 5, mais pas tout à fait, de sorte que vous auriez à tester les diviseurs 2, 3 et 4 (ils seraient générer de 12, 8 et 6, respectivement). Si vous enlevez toutes les puissances de deux, vous êtes de gauche avec 3. Juste à 3. La racine carrée de 3 à moins de 2 de sorte que vous n'avez pas besoin de test aucun diviseurs. Donc, vous êtes passé de 3 lent divisions à zéro divisions + un couple de quarts de travail (d'abord à supprimer les puissances de deux, puis plus tard à rajouter). Une victoire éclatante.
- comme pour la combinaison: vous auriez 3 puissances de 2: 2, 4 et 8. Ce sont tous des diviseurs. Maintenant, multipliez par 3 ("tous" les autres diviseurs, dont il arrive à être un seul), pour obtenir 6, 12 et 24. Alors jetez 24 parce que c'est pas une bonne diviseur.
InformationsquelleAutor harold
0

Code présenté dans l'une des réponses a un bug qui est difficile à voir au premier coup d'œil. Si sqrt(n) est valide diviseur; mais n n'est pas un carré parfait numéro,puis deux résultats sont omis.

E. g. Essayez n = 15, et de voir ce qui se passe; sqrt(15) = 3, de sorte que la dernière valeur de la boucle while est 2. La prochaine instruction exécutée if (i * i == n) sera exécuté comme if(3 * 3 == 15). Donc 3 n'est pas répertorié comme un diviseur, aussi 5 a été manquée.

La suite va traiter le cas général d'entiers positifs correctement.
```
 {
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();
}
```
InformationsquelleAutor Duckman

  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;

InformationsquelleAutor Himanshu Jain

Quand le nombre est impair, on peut même passer le même nombre.
Une légère improvisation dans le code accepté 🙂

Ici le code Java pour trouver les facteurs d'un nombre donné.

import java.util.Scanner;
public class Factors {
public static void main(String[] 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 + ", ");
}
}
}
}
}
}
}

InformationsquelleAutor manohar e

C'est ma nouvelle Version de C#. Grâce à Rndm c'est près de 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;
}

InformationsquelleAutor AustrianHunter

Vous devez vous connecter pour publier un commentaire.