By checking the square root outside of the select statement, you will save the processor a number of extra calculations.  I modified it to be this:

 SELECT @NextIntSqrt = SQRT(@NextInt)

 IF NOT EXISTS (SELECT Prime FROM Primes WHERE @NextIntSqrt >= Prime AND @NextInt % Prime = 0)

Cuts down the calculation time significantly.  I also adjusted the order of the filters in the WHERE clause.