We use the Subaru Hyper Suprime-Cam (HSC) to conduct a high-cadence (2 min sampling) 7~hour long observation of the Andromeda galaxy (M31) to search for the microlensing magnification of stars in M31 due to intervening primordial black holes (PBHs) in the halo regions of the Milky Way (MW) and M31. The combination of an aperture of 8.2m, a field-of-view of 1.5 degree diameter, and excellent image quality (~ 0.6'') yields an ideal dataset for the microlensing search. If PBHs in the mass range M_PBH = [10^{-13},10^{-6}] Msun make up a dominant contribution to dark matter (DM), the microlensing optical depth for a single star in M31 is tau~10^{4}-10^{-7}, owing to the enormous volume and large mass content between M31 and the Earth. The HSC observation allows us to monitor more than tens of millions of stars in M31 and in this scenario we should find many microlensing events. To test this hypothesis, we extensively use an image subtraction method to efficiently identify candidate variable objects, and then monitor the light curve of each candidate with the high cadence data. Although we successfully identify a number of real variable stars such as eclipse/contact binaries and stellar flares, we find only one possible candidate of PBH microlensing whose genuine nature is yet to be confirmed. We then use this result to derive the most stringent upper bounds on the abundance of PBHs in the mass range. When combined with other observational constraints, our constraint rules out almost all the mass scales for the PBH DM scenario where all PBHs share a single mass scale. (see arXiv:1701.02151)