求兩數是否互質(互素)

利用輾轉相除法求兩數是否互為質數(素數)

1. $a=200;
2. $b=13;
3. //輾轉相除法
4. if($b>$a){
5. $x=$a;$a=$b;$b=$x;
6. }
7. while(1){
8. //echo "a=".$a." b=".$b;echo "\n";
9. if($b==1){echo "互質";break;}
10. if($b==0){echo "不互質";break;}
11. if($a-$b > $b){
12. $a=$a-$b;
13. }else{
14. $a=$a-$b;
15. $x=$a;$a=$b;$b=$x;
16. }
17. }
18. ?>

复制代码