int N[100000] = { ... }
int D[100000] = { ... }

for (int i = 0; i < 100000; i++)
    for (int j = 0; j < 100000; j++)
    {
        int k = gcd(N[i], D[j]); // euclids algorithm

        N[i] /= k;
        D[j] /= k;
    }

// Not very optimised, one could easily leave out the even numbers, or also the multiples of 3
// to reduce space usage and computation time
int *spf_sieve = malloc((limit+1)*sizeof *spf_sieve);
int root = (int)sqrt(limit);
for(i = 1; i <= limit; ++i) {
    spf_sieve[i] = i;
}
for(i = 4; i <= limit; i += 2) {
    spf_sieve[i] = 2;
}
for(i = 3; i <= root; i += 2) {
    if(spf_sieve[i] == i) {
        for(j = i*i, step = 2*i; j <= limit; j += step) {
            if (spf_sieve[j] == j) {
                spf_sieve[j] = i;
            }
        }
    }
}

N[i]=p1^kn1 * p2^kn2 ...
D[i]=p1^kd1 * p2^kd2 ...

Power_N[p1]=sum of kn1 for all i's
Power_D[p1]=sum of kd1 for all i's

Divide the N and D by p1^(min(Power_N[p1],Power_D[p2])) in O(10^5) each