Algoritmo per calcolare il numero di divisori di un determinato numero
https://stackoverflow.com/questions/110344
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Quale sarebbe l'algoritmo più ottimale (dal punto di vista delle prestazioni) per calcolare il numero di divisori di un dato numero?
Sarebbe fantastico se tu potessi fornire uno pseudocodice o un link ad alcuni esempi.
EDIT: tutte le risposte sono state molto utili, grazie. Sto implementando il setaccio di Atkin e poi userò qualcosa di simile a quanto indicato da Jonathan Leffler. Il link pubblicato da Justin Bozonier contiene ulteriori informazioni su ciò che volevo.
Soluzione
Dmitriy ha ragione sul fatto che vorrai che il setaccio di Atkin generi la lista principale, ma non credo che si occupi dell'intera questione. Ora che hai un elenco di numeri primi, devi vedere quanti di questi numeri primi fungono da divisori (e con quale frequenza).
Ecco un po 'di pitone per l'algo Guarda qui e cerca " Oggetto : matematica - algoritmo divisori " ;. Basta contare il numero di elementi nell'elenco invece di restituirli comunque.
Ecco un Dr. Math che spiega esattamente di cosa hai bisogno fare matematicamente.
In sostanza si riduce a se il tuo numero n è:
n = a ^ x * b ^ y * c ^ z
(dove a, b e c sono i divisori primi di n e x, ye z sono il numero di volte che il divisore viene ripetuto)
quindi il conteggio totale per tutti i divisori è:
(x + 1) * (y + 1) * (z + 1) .
Modifica: A proposito, per trovare a, b, c, ecc. ti consigliamo di fare ciò che equivale a un avido algo se lo capisco correttamente. Inizia con il tuo più grande divisore primo e moltiplicalo per se stesso fino a quando un'ulteriore moltiplicazione supererebbe il numero n. Passa quindi al fattore più basso successivo e moltiplica il numero primo ^ precedente di volte in cui è stato moltiplicato per il primo corrente e continua a moltiplicare per il primo fino a quando il successivo non supererà n ... ecc. Tieni traccia del numero di volte in cui moltiplichi il divisori insieme e applicano quei numeri nella formula sopra.
Non sono sicuro al 100% della mia descrizione dell'algo, ma in caso contrario è qualcosa di simile.
Altri suggerimenti
Esistono molte molte tecniche di factoring rispetto al setaccio di Atkin. Ad esempio supponiamo di voler calcolare il fattore 5893. Beh, la sua sqrt è 76,76 ... Ora proveremo a scrivere 5893 come prodotto dei quadrati. Bene (77 * 77 - 5893) = 36 che è 6 quadrati, quindi 5893 = 77 * 77 - 6 * 6 = (77 + 6) (77-6) = 83 * 71. Se ciò non avesse funzionato avremmo verificato se il 78 * 78 - 5893 fosse un quadrato perfetto. E così via. Con questa tecnica è possibile verificare rapidamente i fattori vicino alla radice quadrata di n molto più velocemente rispetto al test dei singoli numeri primi. Se combini questa tecnica per escludere numeri primi di grandi dimensioni con un setaccio, avrai un metodo di factoring molto migliore rispetto al solo setaccio.
E questa è solo una delle tante tecniche che sono state sviluppate. Questo è abbastanza semplice. Ci vorrebbe molto tempo per imparare, diciamo, abbastanza teoria dei numeri per capire le tecniche di factoring basate su curve ellittiche. (So ??che esistono. Non li capisco.)
Pertanto, a meno che tu non abbia a che fare con piccoli numeri interi, non proverei a risolvere questo problema da solo. Invece, proverei a trovare un modo per usare qualcosa come PARI libreria che ha già implementato una soluzione altamente efficiente. Con ciò posso calcolare un numero casuale di 40 cifre come 124321342332143213122323434312213424231341 in circa 0,05 secondi. (La sua fattorizzazione, nel caso te lo chiedessi, è 29 * 439 * 1321 * 157907 * 284749 * 33843676813 * 4857795469949. Sono abbastanza fiducioso che non l'abbia capito usando il setaccio di Atkin ...)
@Yasky
La tua funzione divisori ha un bug in quanto non funziona correttamente per i quadrati perfetti.
Prova:
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;
}
Non sono d'accordo sul fatto che il setaccio di Atkin sia la strada da percorrere, perché potrebbe richiedere più tempo per controllare ogni numero in [1, n] per primalità di quanto non ridurrebbe il numero per divisioni.
Ecco un po 'di codice che, sebbene leggermente più hacker, è generalmente molto più veloce:
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 Funziona con il codice Python per risolvere questo problema.
Questa interessante domanda è molto più difficile di quanto sembri e non ha ricevuto risposta. La domanda può essere considerata in 2 domande molto diverse.
1 dato N, trova l'elenco L dei fattori primi di N
2 dato L, calcola il numero di combinazioni uniche
Tutte le risposte che vedo finora fanno riferimento al n. 1 e non menziono che non è trattabile per numeri enormi. Per N di dimensioni moderate, anche numeri a 64 bit, è facile; per N enorme, il problema del factoring può richiedere "per sempre". La crittografia della chiave pubblica dipende da questo.
La domanda n. 2 necessita di ulteriori discussioni. Se L contiene solo numeri univoci, è un semplice calcolo che utilizza la formula di combinazione per scegliere k oggetti da n elementi. In realtà, è necessario sommare i risultati dall'applicazione della formula variando k da 1 a sizeof (L). Tuttavia, L conterrà di solito più occorrenze di più numeri primi. Ad esempio, L = {2,2,2,3,3,5} è la fattorizzazione di N = 360. Ora questo problema è abbastanza difficile!
Restating # 2, data la raccolta C contenente k articoli, in modo che l'articolo a abbia un 'duplicato, e l'articolo b abbia b' duplicati, ecc. quante combinazioni uniche da 1 a k-1 ci sono? Ad esempio, {2}, {2,2}, {2,2,2}, {2,3}, {2,2,3,3} devono verificarsi ciascuno una volta e una sola volta se L = {2,2 , 2,3,3,5}. Ognuna di queste sotto-collezioni uniche è un divisore unico di N moltiplicando gli articoli nella sotto-raccolta.
Una risposta alla tua domanda dipende molto dalle dimensioni dell'intero. Metodi per piccoli numeri, ad es. meno di 100 bit e per i numeri ~ 1000 bit (come quelli utilizzati nella crittografia) sono completamente diversi.
-
panoramica generale: http://en.wikipedia.org/wiki/Divisor_function
-
valori per
ndi piccole dimensioni e alcuni riferimenti utili: A000005: d (n) (chiamato anche tau (n) o sigma_0 (n)), il numero di divisori di n. -
esempio reale: fattorizzazione di numeri interi
Ecco un algoritmo O (sqrt (n)) semplice. L'ho usato per risolvere euler di progetto
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
SOLO una riga
Ho pensato molto attentamente alla tua domanda e ho cercato di scrivere un pezzo di codice altamente efficiente e performante
Per stampare tutti i divisori di un determinato numero sullo schermo abbiamo bisogno di una sola riga di codice!
(usa l'opzione -std = c99 durante la compilazione tramite 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
per trovare numeri di divisori puoi usare la seguente funzione molto veloce (funziona correttamente per tutti i numeri interi tranne 1 e 2)
int number_of_divisors(int n)
{
int counter,i;
for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
return counter;
}
o se tratti un dato numero come un divisore (funziona correttamente per tutti i numeri interi tranne 1 e 2)
int number_of_divisors(int n)
{
int counter,i;
for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
return ++counter;
}
NOTA: due funzioni sopra funzionano correttamente per tutti i numeri interi positivi tranne i numeri 1 e 2 quindi è funzionale per tutti i numeri maggiori di 2 ma se devi coprire 1 e 2, puoi usare una delle seguenti funzioni (un po 'più lenta)
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;
}
o
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;
}
piccolo è bello :)
Il setaccio di Atkin è una versione ottimizzata del setaccio di Eratostene che fornisce tutti i numeri primi fino a un dato intero. Dovresti essere in grado di cercarlo su Google per maggiori dettagli.
Una volta che hai quell'elenco, è semplice dividere il tuo numero per ogni numero primo per vedere se è un divisore esatto (cioè il resto è zero).
I passaggi di base che calcolano i divisori per un numero (n) sono [questo è pseudocodice convertito da codice reale, quindi spero di non aver introdotto errori]:
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
Potresti provare questo. È un po 'hacker, ma è abbastanza veloce.
def factors(n):
for x in xrange(2,n):
if n%x == 0:
return (x,) + factors(n/x)
return (n,1)
Una volta ottenuta la scomposizione in fattori primi, c'è un modo per trovare il numero di divisori. Aggiungi uno a ciascuno degli esponenti su ogni singolo fattore e quindi moltiplica gli esponenti insieme.
Ad esempio: 36 Fattorizzazione Prime: 2 ^ 2 * 3 ^ 2 Divisori: 1, 2, 3, 4, 6, 9, 12, 18, 36 Numero di divisori: 9
Aggiungine uno a ciascun esponente 2 ^ 3 * 3 ^ 3 Moltiplicare gli esponenti: 3 * 3 = 9
Prima di impegnarti in una soluzione, considera che l'approccio Sieve potrebbe non essere una buona risposta nel caso tipico.
Qualche tempo fa c'era una domanda principale e ho fatto un test del tempo - per gli interi a 32 bit almeno determinare se fosse primo era più lento della forza bruta. Sono in corso due fattori:
1) Mentre un essere umano impiega un po 'di tempo a fare una divisione, è molto veloce sul computer, simile al costo di cercare la risposta.
2) Se non si dispone di una tabella principale, è possibile creare un ciclo che viene eseguito interamente nella cache L1. Questo lo rende più veloce.
Questa è una soluzione efficiente:
#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;
}
I divisori fanno qualcosa di spettacolare: si dividono completamente. Se si desidera controllare il numero di divisori per un numero, n , è chiaramente ridondante coprire l'intero spettro, 1 ... n . Non ho fatto ricerche approfondite per questo, ma ho risolto il problema Project Euler 12 sui numeri triangolari . La mia soluzione per il test maggiore di 500 divisori è stata eseguita per 309504 microsecondi (~ 0,3 secondi). Ho scritto questa funzione divisore per la soluzione.
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;
}
Per ogni algoritmo, c'è un punto debole. Pensavo fosse debole rispetto ai numeri primi. Ma poiché i numeri triangolari non sono stampati, ha funzionato perfettamente. Dal mio profilo, penso che sia andato abbastanza bene.
Buone vacanze.
Desideri il setaccio di Atkin, descritto qui: http://en.wikipedia.org/wiki / Sieve_of_Atkin
il metodo dei numeri primi è molto chiaro qui. P [] è un elenco di numeri primi minori o uguali a 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 .
I libri di testo di teoria dei numeri chiamano la funzione di conteggio dei divisori tau. Il primo fatto interessante è che è moltiplicativo, cioè. t (ab) = t (a) t (b), quando aeb non hanno alcun fattore comune. (Prova: ogni coppia di divisori di aeb dà un distinto divisore di ab).
Ora nota che per p a prime, t (p ** k) = k + 1 (i poteri di p). Quindi puoi facilmente calcolare t (n) dalla sua fattorizzazione.
Tuttavia, la scomposizione in fattori di grandi numeri può essere lenta (la sicurezza della crtoprofia RSA dipende dal fatto che il prodotto di due numeri primi di grandi dimensioni è difficile da scomporre). Ciò suggerisce questo algoritmo ottimizzato
- Verifica se il numero è primo (veloce)
- In tal caso, restituire 2
- Altrimenti, fattorizza il numero (rallenta se multipli grandi fattori primi)
- Calcola t (n) dalla fattorizzazione
Di seguito è riportato un programma C per trovare il numero di divisori di un determinato numero.
La complessità dell'algoritmo sopra è O (sqrt (n)).
Questo algoritmo funzionerà correttamente per il numero che è un quadrato perfetto e per i numeri che non sono un quadrato perfetto.
Nota che il limite superiore del loop è impostato sulla radice quadrata del numero per avere l'algoritmo più efficiente.
Notare che la memorizzazione di upperlimit in una variabile separata consente anche di risparmiare tempo, non si dovrebbe chiamare la funzione sqrt nella sezione condizione del ciclo for, questo risparmia anche il tempo di calcolo.
#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;
}
Invece del precedente ciclo for puoi anche usare il seguente ciclo che è ancora più efficiente in quanto elimina la necessità di trovare la radice quadrata del numero.
for(i=2;i*i<=n;i++)
{
...
}
Ecco una funzione che ho scritto. il tempo peggiore è la complessità O (sqrt (n)), il tempo migliore invece è O (log (n)). Ti dà tutti i divisori primi insieme al numero della sua occorrenza.
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;
}
Questo è il modo più semplice per calcolare il numero divissors:
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
Ho testato il tuo codice e apportato alcuni miglioramenti, ora è ancora più veloce. Ho anche provato con @ & # 1607; & # 1608; & # 1605; & # 1606; & # 1580; & # 1575; & # 1608; & # 1740; & # 1583; & # 1662; & # 1608; & # 1585; codice, anche questo è più veloce del suo codice.
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;
}
Non è solo una questione di factoring del numero - determinare tutti i fattori del numero? Puoi quindi decidere se hai bisogno di tutte le combinazioni di uno o più fattori.
Quindi, un possibile algoritmo sarebbe:
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
Spetta quindi a te combinare i fattori per determinare il resto della risposta.
Questo è qualcosa che mi è venuta in base alla risposta di Justin. Potrebbe richiedere un po 'di ottimizzazione.
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))
Penso che sia quello che stai cercando. Faccio esattamente quello che hai chiesto. Copia e incolla nel Blocco note. Salva come * .bat.Run.Inserisci numero. Moltiplica il processo per 2 e questo è il numero di divisori. L'ho fatto apposta in modo che determini i divisori più velocemente:
Si prega di notare che un CMD vendibile non può supportare valori superiori a 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
Immagino che questo sia utile e preciso
script.pyton
> > > factor = [x per x nell'intervallo (1, n + 1) se n% x == 0]
print len ??(fattori)
Prova qualcosa del genere:
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;
}
È possibile pre-calcolare i numeri primi fino alla radice sqaure della N massima possibile e calcolare l'esponente di ogni fattore primo di un numero. Il numero di divisori di n (n = p1 ^ a p2 ^ b p3 ^ c ...) è (a + 1) (b + 1) (c + 1) perché è uguale al conteggio del modo di combinare il numero primo numeri di questi fattori (e questo conterà il numero di divisori). Questo è molto veloce se precomponi i numeri primi
Informazioni più dettagliate su questo metodo:
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;
}
}
Non conosco il metodo PIÙ efficiente, ma farei quanto segue:
- Crea una tabella di numeri primi per trovare tutti i numeri primi inferiori o uguali alla radice quadrata del numero (Personalmente, userei il setaccio di Atkin)
- Contare tutti i numeri primi inferiori o uguali alla radice quadrata del numero e moltiplicarlo per due. Se la radice quadrata del numero è un numero intero, sottrarre uno dalla variabile di conteggio.
Dovrebbe funzionare \ o /
Se hai bisogno, posso codificare qualcosa domani in C per dimostrarlo.
