CODEWITHSUNDEEP
c++factors
Aagam Shah
Aagam Shah

Reputation: 78

Finding factors

Well I am doing a C++ program and in that I need to find numbers with common factors from an array.I am already doing it in the naive way.

int commonFactors(int p, int q){
    int count = 0;

    if(q > p){
        for(int i = 2;i < q;i++){
            if((q%i==0)&&(p%i==0)){
                count++;
                break;
            }
        }
    }
    else if(p > q){
        for(int i = 2;i < p;i++){
            if((p%i==0)&&(q%i==0)){
                count++;
                break;
            }
        }
    }
    else{
        count = 1;
    }

    return count;
}

Well then my code timeouts for larger inputs. My input range is from 1 to 1000000 for any element in the array. Any clue about how to compute it efficiently?

I have an idea of checking with only prime factors but I am worried about the range in which to check.

Upvotes: 1

Views: 2172

Answers (5)

zstewart
zstewart

Reputation: 2177

If the sole question is "do these two have a common factor (other than one)", then one option would simply be to compute their greatest common divisor, and check if it is one. The GCD can be computed fairly efficiently (definitely faster than just counting all the way up to your numbers) using the Euclidean algorithm:

gcd(a, 0) = a
gcd(a, b) = gcd(b, a % b)

Upvotes: 4

renonsz
renonsz

Reputation: 591

Counting factors from 2 to bigger input is brute force and lasts long even if one of the inputs is large. Number of common divisors could be get from exponents of their prime factorization. Easier to calculate their greatest common divisor first

gcd = gcd( p0, q0 )
/* .. */
int gcd( p0, q0 )
{
    while( q0 )
    {
        int swp = q0;
        q0 = p0 % q0;
        p0 = swp;
    }
    return p0;
}

and then count its divisors

  • in naiv way (as in question)
  • by always dividing gcd with found divisors

  • by prime factorization

    p0^x0 * p1^x1 * .. * pN^xN = gcd
count = (1+x0) * (1+x1) * .. * (1+xN)

Prime factorization requires prime list up to sqrt(gcd).

Upvotes: 0

Serge Ballesta
Serge Ballesta

Reputation: 148870

First some mathematics: Say A and B are two positive not null integers, let us call C= gcd(A, B) the greatest common divisor of A and B, then if M divises both A and B, M divises C.

So if you only want to know whether A and B have common divisors you just have to check whether C is greater than 1, if you want to know all common divisors (or their number) you have to find all divisors of C.

Euclidean's algorithm to find the GCD of two numbers is based on following property: say B < A, A = P * Q + R is the euclidean division of P by Q, then if R = 0, GCD(A,B) = B, else GCD(A,B) = GCD(B,R) (ref wikipedia)

Now some code:

/* Euclidian algorythm to find Greatest Common Divisor
 Constraint (not controled here) p>0 and q>0 */
int gcd(int p, int q) {
    // ensures q < p
    if (p < q) {
        int temp = p;
        p = q;
        q = temp;
    }
    int r = p % q;
    // if q divises q, gcd is q, else gcd(p, q) is gcq(q, r)
    return (r == 0) ? q : gcd(q, r);
}

bool sharedivisors(int p, int q) {
    int d = gcd(p, q);
    return d > 1;
}

int divisors(int p, int q) {
    int d = gcd(p, q);
    if (d == 1) {
        return 1;
    }
    int count = 0;
    for(int i=2; i<d/2; i++) {
        if(d % i == 0) {
            int j = d/i;
            if (j > i) count += 2;
            else {
                if (j == i) count += 1;
                break;
            }
        }
    }
    return count + 2; // and 1 and d
}

Upvotes: 0

YePhIcK
YePhIcK

Reputation: 5856

Consider two numbers: 9240 and 16170. Each number can be written down as a product of a (few) prime numbers:

9240 = 2*2*3*5*7*11
16170 = 2*3*5*7*7*11

From the example above it should be obvious that the total number of possible common factors would be the total list of numbers you can create with those operands. In this case the set of numbers 2, 3, 5, and 11 will produce 15 total combinations.

So your code could do the following steps (I'm not going to write the C++ code for you as you should be able to do so easily yourself):

  1. Split each the number into its prime factors using Integer factorization
  2. Find the complete subset of those primes that are present in each list (don't forget that some may appear more than once in both lists and should be counted as separate ones, i.e. twice)
  3. Find all the possible numbers you can create by combining the given set of primes

For the last part of this you can see Dynamic programming for ideas on how to improve its performance significantly compared to a naïve approach.

Upvotes: 0

in need of help
in need of help

Reputation: 1622

You can do it more efficiently by running the for loop up to "sqrt(p)" (or q, depending on the smaller number of course). That should speed up things already.

Upvotes: 0

Related Questions