Instead of rolling your own, you should use an established password hash, like PBKDF2, scrypt or maybe bcrypt, they try to be more expensive on GPUs and custom cracking hardware. (Argon2 is also an option, but not widely supported yet.)
(this will take about a million times longer compared to the usual method of calling a single hash function)
If you used $n=10^9$, brute force would take a billion times as long. However, that would be really slow to use in practice. My mid range Intel CPU can hash ~10 million SHA-256 / s on one core, meaning a couple of minutes for your $n$. A million is more reasonable.
Does it make sense to store them in the following form instead:?
Your iterated hash is pretty close to being PBKDF1. One important issue is the salt: PBKDF1 requires an eight octet salt. If you allowed arbitrary salts that can differ in length, it would be possible to have $p_1 || s_1 = p_2 || s_2$.
PBKDF1 is only recommended for legacy applications (due to the limited output size) and I would be more comfortable with PBKDF2:
- Each iteration increases the collision rate. If you use a large enough hash function with $\log_2n$ bits of collision resistance to spare, that will not matter in practice, but PBKDF2 avoids it.
- By using HMAC, PBKDF2 benefits from security proofs that show it is potentially secure with some weaker hash functions. Also a theoretical thing unless you use an obsolete/broken hash.