Эффективное получение всех делителей заданного числа

Question

В соответствии с этим post мы можем получить все делители числа через следующие коды.

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

Например, делители числа 24 являются 1 2 3 4 6 8 12 24.

После поиска некоторых связанных должностей я не нашел никаких хороших решений. Есть ли эффективный способ достичь этого?

Мое решение:

1. Найти все простые множители данного числа через этот solution.
2. Получите все возможные комбинации этих простых факторов.

Однако, похоже, что это нехорошо.

Answer 1

Факторы спарены. 1 и 24, 2 и 12, 3 и 8, 4 и 6.

Улучшение вашего алгоритма может состоять в том, чтобы итератировать до квадратного корня num вместо всего пути до num, а затем рассчитать парные коэффициенты, используя num/i.

не

Answer 2

Вы должны действительно проверить до квадратного корня из NUM как SQRT (NUM) * SQRT (число) = NUM:

Что-то на этих линиях:

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

Существует не эффективный способ в том смысле, алгоритмической сложности (алгоритм с полиномиальной сложностью), известный в настоящее время в науке. Таким образом, повторение до тех пор, пока квадратный корень, как уже было предложено, в основном так же хорош, как вы можете быть.

Главным образом из-за этого значительная часть используемой криптографии основана на предположении, что для вычисления простой факторизации любого заданного целого требуется очень много времени.

Answer 4

Существует множество хороших решений для нахождения всех основных факторов не слишком больших чисел. Я просто хотел указать, что, как только у вас есть их, для получения всех факторов не требуется никаких вычислений.

если N = p_1^{a}*p_{2}^{b}*p_{3}^{c}.....

Тогда число факторов явно (a+1)(b+1)(c+1)...., поскольку каждый фактор может orruc нуля до времени.

например. 12 = 2^2*3^1 поэтому он имеет 3*2 = 6 факторов. 1,2,3,4,6,12

======

Первоначально я думал, что вы просто хотели количество различных факторов. Но та же логика применяется. Вы просто перебираете множество чисел, соответствующих возможным комбинациям показателей.

так Int он приведенный выше пример:

00 
01 
10 
11 
20 
21 

дает вам 6 факторы.

Answer 5

Вот мой код:

#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(); 
    } 
} 

Первая часть, сито() используется для нахождения простых чисел и поместить их в простых числах [] массиве. Перейдите по ссылке, чтобы узнать больше об этом коде (побитное сито).

Вторая часть primeFactors (x) принимает в качестве входных данных целое число (x) и обнаруживает его простые множители и соответствующий показатель и помещает их в векторные факторы []. Например, primeFactors (12) заполнит факторы [] следующим образом:

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

как 12 = 2^2 * 3^1

The setDivisors третья часть() рекурсивно вызывает себя, чтобы вычислить все делители х, используя векторные множители [] и помещая их в векторные делители [].

Он может вычислять дивизоры любого числа, которое вписывается в int. И это довольно быстро.

Answer 6

for(int i = 1; i * i <= num; i++) {/ * upto sqrt - это потому, что все число после sqrt также определяется, когда число делится на i. Например, если число равно 90, когда оно делится на 5, вы также можете увидеть, что 90/5 = 18, где 18 также делит число , но когда число является идеальным квадратом, то num/i == i только i является фактором */

Answer 7

мы можем также обратиться к использованию простых множителей в ряде Например :::

 100  
    /\ 
    10 10 
/\/\ 
    2 5 5 2 

, таким образом, мы имеем (2^2) (5^2) отсюда мы добавим каждый 1 к полномочия 2 и 5. Теперь мы имеем 3 * 3 = 9 как общее число факторов 100 (а именно 1, 2,4,5,10,20,25,50,100) Таким образом, мы можем использовать этот подход для нахождения факторов очень больших чисел и в конечном итоге уменьшить количество итераций.

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

Answer 10

Я сделал один с более простыми понятиями, но все еще работает отлично

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