正直、ベルトラン＝チェビシェフの定理を証明しないと、きちんと証明したことにはならないと思うよ。
エルデシュの証明は短かったかもしれないけど、それ以外の証明はかなり難しそうだった。