Algoritmo per trovare tutti i divisori esatti di un intero dato

Voglio trovare tutti i divisori esatti di un numero. Attualmente ho questo:

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

C’è un modo per migliorarlo?

Innanzitutto, il tuo codice dovrebbe avere la condizione di i <= n/2 , altrimenti potrebbe perdere uno dei fattori, ad esempio 6 non verrà stampato se n = 12.

Esegui il ciclo sulla radice quadrata del numero (ad esempio i <= sqrt(n) ) e stampa sia i che n/i (entrambi saranno multipli di 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(); } 

Nota :

  • Per un quadrato perfetto, in modo che la radice quadrata non venga stampata due volte, il controllo aggiuntivo viene eseguito alla fine del ciclo per i*i == n come suggerito da @chepner.
  • Se si desidera che tutti i fattori in ordine crescente memorizzino i valori in una matrice, alla fine del ciclo ordinano tutti i numeri e la visualizzazione.

Trovare tutti i divisori usando “trovare tutti i fattori primi” in C (più veloce) e fino a 18 cifre.

 #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 semplice ricerca lineare può essere migliorata eliminando prima tutti i fattori di 2. Ciò può essere fatto semplicemente spostando i bit, o contando gli zero di addestramento con una bella funzione intrinseca. Questo è molto veloce in entrambi i casi. Quindi esegui l’algoritmo suggerito da shg (che verrà eseguito molto più velocemente ora che le potenze di due non sono presenti) e combinerai il risultato con tutti i possibili poteri di due (non dimenticare questo passaggio). Aiuta molto per gli input che hanno un sacco di formazione zero, ma aiuta anche se non lo fanno – non dovresti più testare alcun divisore pari, quindi il ciclo diventa mezzo lungo.

Può anche aiutare a lanciare alcuni fattori bassi costanti (ma più grandi di 2). Modulo con una costante è quasi certamente ottimizzato dal compilatore (o se no, puoi farlo da solo), ma soprattutto, significa che ci sono meno divisori da testare. Non dimenticare di combinare quel fattore con i divisori che trovi.

Puoi anche ridimensionare completamente il numero (usa il tuo algoritmo preferito – probabilmente Pollho’s Rho sarebbe il migliore) e poi stampare tutti i prodotti (eccetto il prodotto vuoto e il prodotto completo) dei fattori. Questo ha una buona possibilità di finire per essere più veloce per gli input più grandi – L’algoritmo Rho di Pollard trova i fattori molto velocemente rispetto a una semplice ricerca lineare, di solito ci sono meno fattori dei divisori appropriati e l’ultimo passaggio (enumerazione dei prodotti) richiede solo matematica veloce (nessuna divisione). Questo aiuta soprattutto i numeri con fattori molto piccoli, che Rho trova il più veloce.

Il codice presentato in una delle risposte ha un bug che è difficile vedere a prima vista. Se sqrt (n) è un divisore valido; ma n non è un numero quadrato perfetto, quindi vengono omessi due risultati.

Ad esempio, prova n = 15 , e guarda cosa succede; sqrt(15) = 3 , quindi l’ultimo valore del ciclo while è 2. La successiva istruzione eseguita if (i * i == n) verrà eseguita come if(3 * 3 == 15) . Quindi 3 non è elencato come divisore, anche 5 sono stati persi.

Quanto segue gestirà correttamente il caso generale di numeri interi positivi.

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

Quando il numero dato è dispari possiamo persino saltare numeri pari. Una leggera improvvisazione nel codice accettato 🙂

Qui è il codice Java per trovare i fattori del numero specificato.

 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 + ", "); } } } } } } } 

Questa è la mia nuova versione di C #. Grazie a Rndm è quasi 50 volte più veloce del mio primo tentativo.

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