The poor ductility of hcp Mg is attributed to the low activity of non-basal slip systems and so activation of prismatic slip can aid ductility in rolled sheets by providing three additional < a > Burgers vector slip systems. Experimental studies show that dilute additions of alloying elements such as Zn and Al leads to softening of prismatic slip at low temperatures but strengthening at higher temperatures. Here, the role of solute strengthening of prismatic edge dislocations is investigated as a possible explanation for the higher-T strengthening. Mg-Zn is studied using first-principles inputs in a parameter-free solute strengthening theory. First-principles DFT is necessary to accurately assess the strong solute chemical interaction energies in the core of the compact edge dislocation. Such calculations are subtle due to motion of the dislocation in the presence of the solute, and methods to obtain reliable results with acceptable computational cost are discussed. While interaction energies of Zn in the prism edge core can be quite large ( +/- 0.34 eV), the edge solute strengthening of prismatic slip in dilute Mg-Zn remains well below experiments at high temperatures. However, the large difference (0.68 eV) in Zn/dislocation interaction energies across the core of the edge dislocation suggests strengthening by dynamic strain aging as an explanation for the higher-T strengthening.