算法中的数学一：判定质数和求约数相关

1.试除法求质数

? ? 质数就是大于1的整数中除了1和自身没有其他因数的数

1.1暴力求解

? ? ?暴力求解的思路就是从2遍历到自身判断是否有被整除的数，时间复杂度为O(n)的

bool is_prime(int x)
{
    if(x<2)return false;
    for(int i=2;i<x;i++)
    {
      if(x%i==0)
      {
         return false;
      }
    }
  return true;
}

1.2调用sqrt库函数

? ? ?因数是成对出现的，如果d是x的因数，则x/d也是x的因数，又因为d<=x/d，则有d^2<=x，所以我们只需要遍历到根号x即可，如果在此之前没有因数，则往后也不会有，因为因数是成对出现的

bool is_prime(int x)
{
    if(x<2)return false;
    for(int i=2;i<sqrt(x);i++)
    {
      if(x%i==0)
      {
         return false;
      }
    }
  return true;
}

? ? ?我们也可以不调用库函数，而转化为i*i<=x的形式，这和开根号的思路是一样的，但是有一个问题，就是在x很大时，i*i会很大，造成溢出，这是很容易出现的问题，而调用库函数往往效率也是比较低的，所以我们必须要优化！

1.3试除法

? ? ?刚才我们提到如果d是x的因数，x/d也是x的因数，当其中一个存在时，另一个也必然存在；如果其中一个不存在，那么另一个也不存在，所以判断前面那一个就行了。

bool is_prime(int x)
{
    if(x<2)return false;
    for(int i=2;i<=x/i;i++)
    {
      if(x%i==0)
      {
         return false;
      }
    }
  return true;
}

? ? ? 这样就将时间复杂度从O(n)降到了O(sqrt(n))。

2.试除法求约数

? ? 前面我们知道如果d是x的因数，则x/i也是x的因数，所以我们只需要遍历前一部分即可，当i是x的因数时，我们要判断i是否等于x/i，如果不等于，就加入x/i，否则不加。

vector<int> get_divisors(int x)
{
	vector<int>res;
	for (int i = 1; i <= x / i; i++)
	{
		if (x % i == 0)
		{
			res.push_back(i);
			if (x != x / i)res.push_back(x / i);
		}
	}
	sort(res.begin(), res.end());
	return res;
}

?完整实现

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> get_divisors(int x)
{
	vector<int>res;
	for (int i = 1; i <= x / i; i++)
	{
		if (x % i == 0)
		{
			res.push_back(i);
			if (x != x / i)res.push_back(x / i);
		}
	}
	sort(res.begin(), res.end());
	return res;
}
int main()
{
	int x;
	cout << "请输入一个整数:" << endl;
	cin >> x;
	vector<int>res = get_divisors(x);
	cout << "该整数的所有约数为：" ;
	for (auto num : res)
	{
		cout << num << " ";
	}
	return 0;
}

? ??

?3.欧几里得算法

? ? ?欧几里得算法又叫辗转相除法，用于计算两个非负整数a和b的最大公约数。

? ? ?两个整数的最大公约数是能够同时整除它们的最大正整数。欧几里得算法的原理是：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。怎么来证明呢？方法如下：

设a、b且a>b,则有a=kb+r(k,r>0)
设a,b最大公约数为v,则有a=xv,b=yv(x,y>0)
                  所以r=a-kb=xv-kyv=(x-ky)v,得到r整除v
设b,r最大公约数为v,则有b=mv,r=nv(m,n>0)
                  所以a=kb+r=kmv+nv=(km+n)v,得到a整除v
所以(a,b)的最大公约数=(b,r)的最大公约数=(b,a%b)的最大公约数

3.1.代码实现

int gcd(int a,int b)
{
   return b?gcd(b,a%b):a;
}

3.2.演示

#include<stdio.h>
int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}
int main()
{
	int a, b;
	printf("请输入两个整数:");
	scanf_s("%d %d", &a, &b);
	printf("a和b的最大公约数为：%d", gcd(a, b));
	return 0;
}