>>146
示されている方法でSATを解くと、
組み合わせ分を試すわけなので指数オーダーになるよ。
AKS素数判定法での計算量は (Wikiによると) \tild{O}(log(n)^7.5) っぽい。
でも、実際には使われてないだろうなー