user5956891 user5956891 - 18 days ago 6
Java Question

Count number of non-prime pairs that when multiplied form a given number N,

A non-prime pair which forms N is 2 different non-prime numbers where the product of the numbers is N.

1<=N<=10^6

For example For N = 24 there are 2 good pairs (non-prime pairs that form N) (4,6), (1,24), but (2,12), (3,8) are not good.

Note: for any 2 numbers a and b pair(a,b) = pair(b,a).

There is another condition which states that if the number is a special number, so output = -1 otherwise count the number of non-primes.

Number is called special number if it can be represented as a product of three prime numbers. Example: 12 is a special number because 12=2*2*3;

I tried brute-force approach using https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ,
which takes O(N*log(log(N)).

"Is there any more optimized way to solve it except brute-force?"

Any idea will be appreciated.

Thanks in advance.

Answer

First of all, Eratosthenes' sieve is O(N*log(log(N)) to list all primes below or equal N (when well implemented).

Second: suppose you factored your number in Q primes with multiplicity which, without sieving, is a process of O(sqrt(N)) at worst (worst: your number is prime). So you have a map of:

  • p0 -> multiplicity m0
  • p1 -> multiplicity m1
  • ...
  • pQ -> multiplicity mQ

How many divisors made from multiplying at least 2 prime factors?

Well, there will be ((m0+1)*(m1+1)*...*(mQ+1) - 2*Q)/2 of them [correction here]

See here for the first product **.

Now, why -2*Q and /2?

The problem required pairs no matter the symmetry of them. So:

  • when I'm excluding one prime divisor, I'm actually excluding 2 pairs - (px * N/px) and (N/px * px). So, when I'm excluding Q primes as non-composite factors, I'm excluding 2*Q pairs
  • similarly, when including something in the result but irrespective of the order of terms, I'll have the two (px * N/px) and (N/px * px) pairs counted as 1.

** if you cannot stomach the math notations in the linked, here's a high-school level way to explain this:

  • {1, p0, p02, ...p0m0} are m0+1 ways of generating divisors with the powers of p0
  • {1, p1, p12, ...p1m1} are m1+1 ways of generating divisors with the powers of p1
  • ...
  • {1, p1, p1Q, ...p1mQ} are mQ+1 ways of generating divisors with the powers of pQ

The number of all combinations (as 1 is already included in each set) will be the cardinality of the cartesian product of all the above subsets - thus the product of the individual cardinalities.


Code - Java

static void factor(long N, Map<Long, Short> primesWithMultiplicity) {
  // some arg checking and trivial cases
  if(N<0) N=-N;
  if(0==N) {
     throw new IllegalArgumentException(
       "Are you kidding me? Every number divides 0, "+
       "you really want them all listed?"
     );
  }
  if(1==N) {
    primesWithMultiplicity.put(1,(short)1);
    return;
  }

   // don't try divisors higher than sqrt(N), 
  // if they would have been detected by their composite-complement 
  for(long div=2; div*div < N; ) {
    short multiplicity=0;
    while((N % div)==0) {
      multiplicity++;
      N /= div; // reduce N
    }
    if(multiplicity>0) {
      primesWithMultiplicity.put(div, multiplicity);
    }
    div+= (div == 2 ? 1 : 2); // from 2 to 3, but then going only on odd numbers
  }
  // done.. well almost, if N is prime, then 
  // trying to divide up to sqrt(N) will lead an empty result. But,
  // in this case, N will still be at original value (as opposed 
  // to being 1 if complete factored)
  if(N>1) {
    primesWithMultiplicity.put(N, 1);
  }
}

int countCompositeDivisors(long N) {
  HashMap<Long, Short> factoringResults=new HashMap<>;
  factor(N, factoringResults);
  int ret=1;
  for(short multiplicity : factoringResults.values()) {
    ret*=(1+multiplicity);
  }
  return (ret-2*factoringResults.size())/2;
}