Find maximal matching in divisibility relation You are given a set of positive integers. You must arrange them into pairs such that:


Each pair contains 2 numbers, one of which is a multiple of another. For example, 8 is a multiple of 4, and 9 is a multiple of 9.
If the same number occurs many times in the initial set, it can be used that many times in the pairs; a number can even be paired with another occurence of the same number
The maximum possible number of pairs is obtained.


Output must be the number of pairs. Shortest code wins.

Sample data

2,3,4,8,9,18 -> 3

7,14,28,42,56 -> 2

7,1,9,9,4,9,9,1,3,9,8,5 -> 6

8,88,888,8888,88888,888888 -> 3

2,6,7,17,16,35,15,9,83,7 -> 2
Haskell, 109 107 76 70 bytes

Thanks to nimi for saving 33 bytes and teaching me some more Haskell. :)
Thanks to xnor for saving another 6 bytes.

import Data.List
f l=maximum$0:[1+f t|a:b:t&lt;-permutations l,a`mod`b&lt;1]


Yay, my first Haskell golf. It works the same as all the answers so far (well, not quite: it only counts the length of the longest prefix of valid pairs in each permutation, but that's equivalent and is actually what my original CJam code did).

For extra golfitude it's also extra inefficient by recursively generating all permutations of the suffix each time the first two elements of a permutation are a valid pair.