user5956891 - 1 year ago 64

Java Question

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 Source

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:

- p
_{0}-> multiplicity m_{0} - p
_{1}-> multiplicity m_{1} - ...
- p
_{Q}-> multiplicity m_{Q}

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 - (p
_{x}* N/p_{x})*and*(N/p_{x}* p_{x}). 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 (p_{x}* N/p_{x})*and*(N/p_{x}* p_{x}) 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, p0
^{2}, ...p0^{m0}} are`m0+1`

ways of generating divisors with the powers of`p0`

- {1, p1, p1
^{2}, ...p1^{m1}} are`m1+1`

ways of generating divisors with the powers of`p1`

- ...
- {1, p1, p1
^{Q}, ...p1^{mQ}} 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;
}
```