求最大公约数和判断素数的最优算法

要求时间限制在1s之内的，测试数据最大到10的5次方，算法思想或者程序代码（C++或c）

判断素数只需要把除数从2变到n的平方根就行了，最大公约数也就一样了