[math-fun] Primes in a square

Sorry if this has all been covered, but: The existence of a prime in every row of the n x n square of lexically ordered numbers 1 through n^2 follows if the largest run of composites on [1, n^2] is less than n. Empirically, this seems to be true for all n > 2 except n = 12 or 13, in which case there is the run of 13 nonprimes [114, 126] on [1, n^2]. I was hoping that there might be some useful asymptotics on prime gaps, specifically, I was hoping that the size of prime gaps near n were known to be less than O(sqrt(n)), but reflection tells me that this is probably not known, otherwise we would have a prime between n^2 and (n+1)^2 for sufficient n. Wild goose chase, oh well.