Python, 9393 91 chars

Naive prime checking (check if divisible by anything from 2 to n (less chars than to n/2)):

g=0;i=l=2
while 1:
 i+=1
 if all(i%x for x in range(2,i/2)):
    if i-l>g:g=i-l;print l,i,g
    l=i

Second level of indent is one tab character.

Output:

2 3 1
5 7 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
...