えーーと、
今読んでる本によく似たのが書いてある。

n が素数かどうか判定するには
n の平方根まで探索すればいい、とある。

つまり ループ継続条件 は
tmp * tmp <= search
で、

あと、ループに入る前の段階で
偶数かどうか調べて
偶数だとそれが2であれば素数、それ以外素数でない return
をやって、

ループの初期条件で tmp に 3 を設定して
増分は奇数だけ総当たりするので tmp +=2

いちばん速いのは、
最初から素数の表を準備する、または
配列に、見つかった素数を逐次登録・再利用して
nの平方根までの素数だけを調べる...らしい。