wake-up-neo.com

Effektiv alle Teiler einer bestimmten Anzahl erhalten

Nach diesem post können wir alle Teiler einer Nummer durch die folgenden Codes erhalten.

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

Die Teiler der Nummer 24 sind beispielsweise 1 2 3 4 6 8 12 24.

Nach dem Durchsuchen einiger verwandter Beiträge habe ich keine guten Lösungen gefunden. Gibt es einen effizienten Weg, dies zu erreichen?

Meine Lösung:

  1. Finden Sie alle Primfaktoren der angegebenen Zahl durch diese Lösung .
  2. Holen Sie sich alle möglichen Kombinationen dieser Primfaktoren.

Es scheint jedoch nicht gut zu sein.

47
zangw

Faktoren sind gepaart. 1 und 24, 2 und 12, 3 und 8, 4 und 6

Eine Verbesserung Ihres Algorithmus könnte darin bestehen, die Quadratwurzel von num anstelle von num zu durchlaufen und dann die paarweisen Faktoren mit num / i zu berechnen.

73
Yu Hao

Sie sollten wirklich die Quadratwurzel von num als sqrt (num) überprüfen. * Sqrt (num) = num:

Etwas in diesen Zeilen:

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';
}
27
SMA

Ein effizienter Weg im Sinne der algorithmischen Komplexität (ein Algorithmus mit polynomischer Komplexität) ist in der Wissenschaft bisher nicht bekannt. So zu iterieren, bis die Quadratwurzel, wie bereits vorgeschlagen, meistens so gut ist, wie Sie nur sein können.

Hauptsächlich aus diesem Grund basiert ein großer Teil der derzeit verwendeten Kryptographie auf der Annahme, dass es sehr zeitaufwendig ist, eine Primfaktorisierung einer gegebenen ganzen Zahl zu berechnen.

13
SpaceTrucker

Hier ist mein Code: 

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

Der erste Teil, sieb (), wird verwendet, um die Primzahlen zu finden und sie in ein primes [] -Array zu setzen. Folgen Sie dem Link, um mehr über diesen Code zu erfahren (Bitweises Sieb).

Der zweite Teil primeFactors (x) nimmt eine Ganzzahl (x) als Eingabe, ermittelt die Primfaktoren und den zugehörigen Exponenten und setzt sie in Vektorfaktoren []. Beispiel: primeFactors (12) füllt die Faktoren [] auf folgende Weise auf: 

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

als 12 = 2 ^ 2 * 3 ^ 1

Der dritte Teil setDivisors () ruft sich rekursiv auf, um alle Divisoren von x unter Verwendung der Vektorfaktoren [] zu berechnen, und setzt sie in Vektor-Divisoren [].

Es können Divisoren beliebiger Anzahl berechnet werden, die in int passen. Es ist auch ziemlich schnell.

7
Rocky Johnson

Es gibt viele gute Lösungen, um alle Primfaktoren nicht zu großer Zahlen zu finden. Ich wollte nur darauf hinweisen, dass, sobald Sie sie haben, keine Berechnung erforderlich ist, um alle Faktoren zu erhalten.

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

Dann ist die Anzahl der Faktoren eindeutig (a+1)(b+1)(c+1)...., da jeder Faktor bis zu einem gewissen Grad Null ergeben kann.

z.B. 12 = 2^2*3^1 hat also 3*2 = 6 faktoren. 1,2,3,4,6,12

======

Ich dachte ursprünglich, dass Sie nur die Anzahl der verschiedenen Faktoren wollten. Es gilt jedoch dieselbe Logik. Sie durchlaufen einfach die Menge der Zahlen, die den möglichen Kombinationen von Exponenten entsprechen.

so int er Beispiel oben:

00
01
10
11
20
21

gibt Ihnen die 6 Faktoren.

5
phil_20686
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;
}
0
ying
for (int i = 1; i*i <= num; ++i)
{
    if (num % i == 0)
    cout << i << endl;
    if (num/i!=i)
    cout << num/i << endl;
}
//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] << " ";
}
0
Ragib

Hier ist die Java-Implementierung von this :

public static int countAllFactors(int num)
{
    TreeSet<Integer> tree_set = new TreeSet<Integer>();
    for (int i = 1; i * i <= num; i+=1)
    {
        if (num % i == 0)
        {
            tree_set.add(i);
            tree_set.add(num / i);
        }
    }
    System.out.print(tree_set);
    return tree_set.size();
}
0
Pratik Patil