找100以内的素数，求约数，求两个数的最大公约数

1.100内的素数

bool isPrime(int num)
{
    
	int tmp = sqrt(num);
	//只遍历到开方出，不能被开方左边的数整除，则一定不能被开方右边的数整除
	for (int i = 2; i <= tmp; i++)
	{
    
		if (num %i == 0)
			return false;
	}
return true;
int main()
{
    
	int n = 100;
	for(int i = 0 ; i <= 100 ; i++)
	{
    
		if(ifPrime(i))
		{
    
			//....
		}
	}
}

2.求一个数除了1和本身的约数

void GetDiv(vector<int> &div, int num)
{
    
    for(int i = 2 ; i <= sqrt(num) ; i++)
    {
    
        if(num % i == 0)
        {
    
            div.push_back(i);
            //以16为例 当2满足了， 需要判断16/2 即8是否满足，满足就存起来。但如果是4这种情况只需存一次就可以
            if(num / i != i)
            {
    
                div.push_back(num / i);
            }
        }
    }
}

3.求两个数的最大公约数
用大数对小数求余，若余数为0，则除数为最大公约数。若余数不为0，将此余数作为除数，小数作为被除数，重新求余，直到余数为0为止。此时的最大公约数为余数。

//辗转相除法
int GCD(int a, int b)
{
    
	if(a<b)
		swap(a,b);
    int c;
    while(c = a % b)
    {
    
        a = b;
        b = c;
    }
    return b;
}