/* Solovey--Strassen法に基づく素数判定 */
int isPrimeSS(int p) {
int i, j;
for(i = 0; i < LOOP; i++) {
int a = rand() % (p -2) +2, b, y = 1, z = 1, q = p;
/* y = a^((p-1)/2) mod p の算出 */
y = calcSqMul(a, (p-1)/2, p);
if(y > 1) y -= p;
/* z = (a/p) の算出（ヤコビ数の算出） */
while(a > 2) {
if(a % 2 == 0) {
a /= 2;
if(q % 8 != 1 && q % 8 != 7) z *= -1;
}
else {
if(a % 4 == 3 && q % 4 == 3) z *= -1;
b = a; a = q; q = b;
a %= q;
}
}
if(a == 0) z = 0;
else if(a == 2 && q % 8 != 1 && q % 8 != 7) z *= -1;
if(y != z) return 0;
}
return 1;
}
-----ここまで

これ以外の関数は、最初のものと同じで大丈夫（のはず）。
おでかけの時間となりましたので、何かあっても自分でがんばよろ。