Professor X and Grouping of Numbers
All submissions for this problem are available.
Upon his first meeting with Laura, Professor X has got a problem for her. Although her exceptional skills are already visible, the professor wants to test her intellectual skills.
So, Professor X gives Laura an array A consisting of N natural numbers. The task for Laura is to distribute these N numbers into some groups such that for any 2 numbers of different groups, the Greatest Common Divisor of both numbers must be 1. Laura has to maximise the number of such groups possible and output the count of groups. Can you help Laura with this problem ?
First line of the input contains N, the size of the array.
Next line contains N natural numbers A1, A2, A3, ........, AN, the elements of the array.
The only line of output must contain the number of such groups possible.
- 1 ≤ N ≤ 106
- 2 ≤ Ai ≤ 107
Input: 8 2 5 13 9 7 25 21 6 Output: 3
Input: 9 60 12 30 24 58 33 18 25 16 Output: 1
Example case 1. In this case, maximum 3 groups having the mentioned property, can be formed: [2,6,7,9,21], , [5,25].
Example case 2. In this case, only 1 group can be formed. There is no way to form 2 or more groups such that any two numbers of different groups have Greatest Common Divisor as 1.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions