c++ - tiene - Obtener de manera eficiente todos los divisores de un número determinado

divisores de un numero ejercicios

Question

De acuerdo con esta post , podemos obtener todos los divisores de un número a través de los siguientes códigos.

for (int i = 1; i <= num; ++i){
    if (num % i == 0)
        cout << i << endl;
}

Por ejemplo, los divisores del número 24 son 1 2 3 4 6 8 12 24 .

Después de buscar algunas publicaciones relacionadas, no encontré ninguna buena solución. ¿Hay alguna manera eficiente de lograr esto?

Mi solución:

1. Encuentre todos los factores primos del número dado a través de esta solution .
2. Obtenga todas las combinaciones posibles de esos factores primos.

Sin embargo, no parece ser una buena.

Answer 1

Aquí está mi código:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define pii pair<int, int>

#define MAX 46656
#define LMT 216
#define LEN 4830
#define RNG 100032

unsigned base[MAX / 64], segment[RNG / 64], primes[LEN];

#define sq(x) ((x)*(x))
#define mset(x,v) memset(x,v,sizeof(x))
#define chkC(x,n) (x[n>>6]&(1<<((n>>1)&31)))
#define setC(x,n) (x[n>>6]|=(1<<((n>>1)&31)))

// http://zobayer.blogspot.com/2009/09/segmented-sieve.html
void sieve()
{
    unsigned i, j, k;
    for (i = 3; i<LMT; i += 2)
        if (!chkC(base, i))
            for (j = i*i, k = i << 1; j<MAX; j += k)
                setC(base, j);
    primes[0] = 2;
    for (i = 3, j = 1; i<MAX; i += 2)
        if (!chkC(base, i))
            primes[j++] = i;
}


//http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
vector <pii> factors;
void primeFactors(int num)
{
    int expo = 0;   
    for (int i = 0; primes[i] <= sqrt(num); i++)
    {
        expo = 0;
        int prime = primes[i];
        while (num % prime == 0){
            expo++;
            num = num / prime;
        }
        if (expo>0)
            factors.push_back(make_pair(prime, expo));
    }

    if ( num >= 2)
        factors.push_back(make_pair(num, 1));

}

vector <int> divisors;
void setDivisors(int n, int i) {
    int j, x, k;
    for (j = i; j<factors.size(); j++) {
        x = factors[j].first * n;
        for (k = 0; k<factors[j].second; k++) {
            divisors.push_back(x);
            setDivisors(x, j + 1);
            x *= factors[j].first;
        }
    }
}

int main() {

    sieve();
    int n, x, i; 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        primeFactors(x);
        setDivisors(1, 0);
        divisors.push_back(1);
        sort(divisors.begin(), divisors.end());
        cout << divisors.size() << "/n";
        for (int j = 0; j < divisors.size(); j++) {
            cout << divisors[j] << " "; 
        }
        cout << "/n";
        divisors.clear();
        factors.clear();
    }
}

La primera parte, tamiz () se usa para buscar los números primos y ponerlos en la matriz de primos []. Siga el enlace para obtener más información sobre ese código (tamiz bit a bit).

La segunda parte primeFactors (x) toma un entero (x) como entrada y descubre sus factores primos y su exponente correspondiente, y los pone en factores vectoriales []. Por ejemplo, primeFactors (12) rellenará factores [] de esta manera:

factors[0].first=2, factors[0].second=2
factors[1].first=3, factors[1].second=1

como 12 = 2 ^ 2 * 3 ^ 1

La tercera parte setDivisors () recurrentemente se llama a sí mismo para calcular todos los divisores de x, usando los factores vectoriales [] y los pone en divisores vectoriales [].

Puede calcular divisores de cualquier número que se ajuste en int. También es bastante rápido.

Answer 2

Deberías comprobar realmente hasta la raíz cuadrada de num como sqrt (num) * sqrt (num) = num:

Algo en estas líneas:

int square_root = (int) sqrt(num) + 1;
for (int i = 1; i < square_root; i++) { 
    if (num % i == 0&&i*i!=num)
        cout << i << num/i << endl;
    if (num % i == 0&&i*i==num)
        cout << i << ''/n'';
}

Answer 3

Existen muchas buenas soluciones para encontrar todos los factores primos de números no demasiado grandes. Solo quería señalar que una vez que los tiene, no se requiere computación para obtener todos los factores.

si N = p_1^{a}*p_{2}^{b}*p_{3}^{c}.....

Entonces el número de factores es claramente (a+1)(b+1)(c+1).... ya que cada factor puede orruc cero hasta veces.

por ejemplo, 12 = 2^2*3^1 por lo que tiene 3*2 = 6 factores. 1,2,3,4,6,12

======

Originalmente pensé que solo querías la cantidad de factores distintos. Pero la misma lógica aplica. Simplemente itera sobre el conjunto de números correspondientes a las posibles combinaciones de exponentes.

tan int el ejemplo de arriba:

00
01
10
11
20
21

te da los 6 factores.

Answer 4

He hecho uno con conceptos más simples, pero sigue funcionando bien

enter code here 
#include <iostream>
#include <stdio.h>
#include <math.h>

bool loop = true;
int x,y,z=1;
using namespace std;

void menu(){
cout << "/n Inserisci il numero da anaizzare : "; #it insetrs the number 
that will be analised
cin >> x;
}
void algoritmo(){
for (int y=1;y<=x;y++){
    if (x%y!=0){
        y++;
    }
    else{
        cout << " " << y;
    }
}
}

int main(){
while (loop == true){
    menu(); #this is the void for the menu
    algoritmo(); #this is the void the algorithm
}
return 0;
}

Answer 5

Los factores están emparejados. 1 y 24 , 2 y 12 , 3 y 8 , 4 y 6 .

Una mejora de su algoritmo podría ser iterar a la raíz cuadrada de num lugar de hasta llegar a num , y luego calcular los factores emparejados usando num / i .

Answer 6

No existe una forma eficiente en el sentido de complejidad algorítmica (un algoritmo con complejidad polinómica) conocida en la ciencia por el momento. Por lo tanto, iterar hasta que la raíz cuadrada como ya se sugirió es casi tan buena como puede ser.

Principalmente debido a esto, una gran parte de la criptografía utilizada actualmente se basa en la suposición de que es muy lento calcular una factorización prima de cualquier entero dado.

Answer 7

for( int i = 1; i * i <= num; i++ ) {/ * upto sqrt es porque todos los números después de sqrt también se encuentran cuando el número se divide por i. EJEMPLO, como si el número es 90 cuando está dividido por 5, también puedes ver que 90/5 = 18 donde 18 también divide el número, pero cuando el número es cuadrado perfecto, entonces num / i == i por lo tanto, solo yo es el factor * /

Answer 8

//Try this,it can find divisors of verrrrrrrrrry big numbers (pretty efficiently :-))
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<conio.h>

using namespace std;

vector<double> D;

void divs(double N);
double mod(double &n1, double &n2);
void push(double N);
void show();

int main()
{
    double N; 
    cout << "/n Enter number: "; cin >> N;

    divs(N); // find and push divisors to D

    cout << "/n Divisors of "<<N<<": "; show(); // show contents of D (all divisors of N)

_getch(); // used visual studio, if it isn''t supported replace it by "getch();"
return(0);
}

void divs(double N)
{
    for (double i = 1; i <= sqrt(N); ++i)
    {
        if (!mod(N, i)) { push(i); if(i*i!=N) push(N / i); }
    }
}

double mod(double &n1, double &n2)
{
    return(((n1/n2)-floor(n1/n2))*n2);
}

void push(double N)
{
    double s = 1, e = D.size(), m = floor((s + e) / 2);
    while (s <= e)
    {   
        if (N==D[m-1]) { return; }
        else if (N > D[m-1]) { s = m + 1; }
        else { e = m - 1; }
        m = floor((s + e) / 2);
    }
    D.insert(D.begin() + m, N);
}

void show()
{
    for (double i = 0; i < D.size(); ++i) cout << D[i] << " ";
}

Answer 9

int result_num;
bool flag;

cout << "Number          Divisors/n";

for (int number = 1; number <= 35; number++)
{
    flag = false;
    cout << setw(3) << number << setw(14);

    for (int i = 1; i <= number; i++) 
    {
        result_num = number % i;

        if (result_num == 0 && flag == true)
        {
            cout << "," << i;
        }

        if (result_num == 0 && flag == false)
        {
            cout << i;
        }

        flag = true;
    }

    cout << endl;   
}
cout << "Press enter to continue.....";
cin.ignore();
return 0;
}