Solving the maximum common divisor

In the foundation of C language, one of the most common problems is to solve the maximum common divisor. First of all, we need to know what the maximum common divisor is (those who have studied in primary school should understand it). I won't go into details here. Secondly, we need to use the most basic code in C language to solve the maximum common divisor. Below I will give three methods for your reference.

1. Method 1: brainless traversal
   The logic of this method is simple. The maximum common divisor between two numbers must not be greater than the smaller one. Therefore, we can use the for loop to divide the two numbers from the smaller one. If the remainder is 0, then this number is the maximum common divisor.
   For example: 18 and 24, the greatest common divisor of these two numbers should be found from 18. When i = 6, both numbers can be divided, and the greatest common divisor is found.
   The code is as follows:

#include <stdio.h>
int main()
{
   	int a, b, tmp;
   	scanf("%d %d", &a, &b);
   	if (a > b)
   	{
   		tmp = a;
   		a = b;
   		b = tmp;
   	}//Fix the size of a and b first
   	for (tmp = a;tmp > 0 ; tmp--)
   		if (a % tmp == 0 && b % tmp == 0)//Find the greatest common divisor
   				break;
   	printf("%d", tmp);
   	return 0;
}

1. Method 2: rolling phase division
   This method is not very direct and requires some mathematical thinking. We now have two numbers, a and B. We might as well assume that a is not less than B, then we can find another number c, so that a = b * n (n is a non negative integer) + c. According to the definition of the greatest common divisor, if both a and B are multiples of this number, then c must also be multiples of this number. Let this number be m.
   Let a = k * m, b = p * m, then c = a - b * n= (k - p * n) * M
   Therefore, c must also be a multiple of this number. Therefore, the problem of the maximum common divisor of a and b is transformed into the maximum common divisor of b and c, that is, the remainder of a divided by b.
   After the mathematical idea is done, let's take a look at the code implementation method

#include <stdio.h>
int main()
{
	int a, b, tmp;
	scanf("%d %d", &a, &b);
	if (a > b)
	{
		tmp = a;
		a = b;
		b = tmp;
	}
	while (tmp)
	{
			tmp = b % a;	
			b = a;
			a = tmp;
	}
	printf("%d\n", b);
	return 0;
}

1. Method 3: recursive implementation
   As a common means, recursion can make the code more concise. Inspired by the previous method, maybe we can use recursion to realize rolling division.

#include <stdio.h>
int recur_gcd(int a,int b);
int main()
{
	int a, b, tmp;
	scanf("%d %d", &a, &b);
	if (a > b)
	{
		tmp = a;
		a = b;
		b = tmp;
	}
	printf("%d\n", recur_gcd(a, b));
	return 0;
}
int recur_gcd(int a, int b)
{
	if (b % a)
		return recur_gcd(b % a, a);
	return a;
}

The above is the recursive algorithm of rolling division. I hope you can learn it

Use a variety of methods to find prime numbers (assuming the range is 100 ~ 200)

Prime numbers, also known as prime numbers, are well known. Prime numbers have no other divisor except themselves and 1. It is worth mentioning that 1 is neither prime nor composite. After establishing this central idea, the rest is also very simple.
Given a range [l, m], what are the methods to find out all prime numbers in this range?

1. Method 1: brainless search
   This method has no technical difficulty. After giving a number k, find out whether there is a number that can divide K by K in [2, k - 1].
   The disadvantage of this method is that if k is large, it will take a lot of time, and RE may occur.
   The code for this method is shown below

int main()
{
	int i = 0;
	int count = 0;
    // The outer loop is used to obtain all data between 100 and 200. 100 is certainly not a prime number, so i starts from 101
	for(i=101; i<=200; i++)
	{
		//Judge whether i is a prime number: divide each data between [2, i) by i. as long as one can be divided, it is not a prime number
		int j = 0;
		for(j=2; j<i; j++)
			if(i%j == 0)
				break;
		// After the above cycle, if j and i are equal, it means that all data between [2, i) cannot be divided by i, then i is a prime number
		if(j==i)
		{
			count++;
			printf("%d ", i);
		}
	}
	printf("\ncount = %d\n", count);
	return 0;
}

Obviously, this method has room for optimization.
2. Method 2: narrow the scope
Further analysis, we find that if a number k is not a prime number, assuming that it is an even number, it must be divisible by 2. If it is not an even number, it can be divisible by an odd number and an odd number, which is equivalent to that the number is more and more toward its center, and the root sign K converges, so the number must find a divisor within the range of [2, k/2]. If not, it must be a prime number.
According to this idea
We can get

int main()
{
	int i = 0;//
	int count = 0;
	for(i=101; i<=200; i++)
	{
		//Judge whether i is prime
		//2->i-1
		int j = 0;
		for(j=2; j<=i/2; j++)
			if(i%j == 0)
				break;
		//...
		if(j>i/2)
		{
			count++;
			printf("%d ", i);
		}
	}
	printf("\ncount = %d\n", count);
	return 0;
}

That is, find the divisor in the range of [2,k/2].
Obviously, you can continue to optimize
As I said before, k = m * n, the two divisors of K are constantly close to the root sign K. therefore, one divisor must be greater than the root sign K and the other less than or equal to the root sign K. therefore, the range can be further reduced to [2, root sign k]
3. Method III further narrowing the scope
Code implementation:

int main()
{
	int i = 0;
	int count = 0；
	for(i=101; i<=200; i++)
	{
		//Judge whether i is prime
		//2->i-1
		int j = 0;
		for(j=2; j<=sqrt(i); j++)
			if(i%j == 0)
				break;
		//...
		if(j>sqrt(i))
		{
			count++;
			printf("%d ", i);
		}
	}
	printf("\ncount = %d\n", count);
	return 0;
}

That's all!
I hope you can gain something after reading it.