A non-prime pair which forms N is 2 different non-prime numbers where the product of the numbers is N.
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.
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:
How many divisors made from multiplying at least 2 prime factors?
Well, there will be
(m0+1)*(m1+1)*...*(mQ+1) - Q of them.
See here for the first product ** ; as for the why
- Q - that's the number of distinct divisors that are simply primes - i.e. not composite.
I trust you will be able to code it or... do you need help with that too?
** if you cannot stomach the math notations in the linked, here's a high-school level way to explain this:
m0+1ways of generating divisors with the powers of
m1+1ways of generating divisors with the powers of
mQ+1ways of generating divisors with the powers of
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.