From the Prime number theorem it will take k tries on average for a k digit number only if you are working in base e and looking at numbers right around e**k. For mortals who work in base 10, it takes an average of about 2.3*k+1 tries or so.

Things like being clever about odds works from this starting point.