There are a total of 4 choose 2 = 6 pairs that can be chosen. This number is small enough to go through each pair one by one.
(1, 2), (1, 3), (1, 4): one divides into every number, so all of these work
(2, 3): 2 does not divide evenly into 3
(2, 4): 2 divides evenly into 4
(3, 4): 3 does not divide evenly into 4
This gives 4 pairs that work for an overall probability of 4/6 = 2/3.