今までの解説を読んで書き直し。

integer n > 1
　1. if ( n is of the form a^b , b > 1 ) output COMPOSITE;// n がa^b で表せるか確認する。
　2. r = 2;// r = 2 から一つずつ調べていく。
　3. while(r < n) {
　4. 　　if ( gcd(n,r) != 1 ) output COMPOSITE;// n,r の最大公約数が1でないか？
　5. 　　if (r is prime)// rが素数の場合
　6. 　　　　let q be the largest prime factor of r - 1;// r-1 の最大の素数、qを探す
　7. 　　　　if ( q>= 4*sqrt(r)*log(n) and ( n^((r-1)/q) != 1 (mod r) ) // 後半はrで割った余りが1でなければ
　8. 　　　　　　　break;
　9. 　　r = r + 1;
　10. }// 最初のループを抜けて、次の一定回数のループで多項式を割った場合の余りを求める。
　11. for a=1 to 2*aqrt(r)*log(n)
　　　　　// x^n-1 で (x-a)^n を割った余りが x^n-a になるか？
　12. 　　if ( (x-a)^n != (x^n -a) (mod x^n - 1,n) ) output COMPOSITE;
　13. output PRIME;

Cで書く際の難点は
　1. if ( n is of the form a^b , b > 1 ) output COMPOSITE;// n がa^b で表せるか確認する。
　4. 　　if ( gcd(n,r) != 1 ) output COMPOSITE;// n,r の最大公約数が1でないか？
　6. 　　　　let q be the largest prime factor of r - 1;// r-1 の最大の素数、qを探す
　12. 　　if ( (x-a)^n != (x^n -a) (mod x^n - 1,n) ) output COMPOSITE;
この４つと思われ。
このうち4.は簡単。
6.もダサいルーチンなら書ける。
面倒そうなのは12.>>106が何やら詳しそうだが力技でなんとかなりそう。
1.は全然想像もできん。お前ら数学の定理かなんか知ってたら教えてくり。