PrimeGCD

Prime and GCD

素数

素数是什么？见小学数学书

如何判断一个数是否是素数？

对于任何正整数，因子总是成对出现。所以只要要判断的数$n$在$2$~$\sqrt{n}$之间没有因子，$n$就是质数

bool isPrime(int a)
{
    if (a < 2)
        return 0;
    for (int i = 2; i * i <= a; ++i)
        if (a % i == 0)
            return 0;
    return 1;
}

GCD

GCD(Greatest Common Divisor) 最大公约数

其实C++有内置的GCD函数，但是因为某种原因，建议不要使用!

再一次翻一翻你的小学数学课本，老师肯定教过你辗转相除求最大公约数

好习惯，使用前先证明：

证明

设$\gcd(x,y)=d$,则此时$x=k_1\cdot d,y=k_2\cdot d$ 且$k_1,k_2$互质

$\therefore \gcd(y,x\% y)=gcd(k_2\cdot d,(k_1\% k_2)\cdot d)$

$\because \gcd(k_2,k_1\% k_2)=1$

$\therefore gcd(y,x\% y)=d$

$\therefore$得证

然后贴个代码：

int gcd(int a, int b) 
{
  	if (b == 0) 
  		return a;
  	return gcd(b, a % b);
}