Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”
This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.
/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * purpose: to find the greatest common divisor of two input analysis: determine the larger or smaller values, and the smaller value of copy. The greatest common divisor can’t exceed the smaller value of two numbers, so start at the smaller value and work down until it’s divisible by both numbers. 24, 18, 24, 17… 25 six platforms: Visual studio 2017 && Windows * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
📝 implementation code 1:
#include<stdio.h>
#pragma warning(disable:4996)
int main(a)
{
int m = 0;
int n = 0;
scanf("%d%d", &m, &n);
// Store the greatest common divisor
int gcd = 0;
// Set the maximum value to m
if (m < n)
{
int temp = m;
m = n;
n = temp;
}
// Suppose the greatest common divisor is n
gcd = n;
while (1)
{
if (m % gcd == 0 && n % gcd == 0)
{
printf("%d\n", gcd);
break; } gcd--; }}Copy the code/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * aim: to optimize the code 1: analysis: You don’t have to make a larger or smaller value, but you have to make a copy of n or M 18 24 18 23… 18 six platforms: Visual studio 2017 && Windows * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
📝 Optimization Code 1:
#include<stdio.h>
#pragma warning(disable:4996)
int main(a)
{
int m = 0;
int n = 0;
scanf("%d%d", &m, &n);
int gcd = 0;
// Suppose the greatest common divisor is m
gcd = m;
while (1)
{
if (m % gcd == 0 && n % gcd == 0)
{
printf("%d\n", gcd);
break; } gcd--; }}Copy the code+++++++++++++++++++++++++++++++++++++++++++++++++++++++++
/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * purpose: Euclidean algorithm for greatest common divisor introduction: Euclid’s algorithm, also known as division of toss and turn, was first described by The Ancient Greek mathematician Euclid in his book The Elements, so it is named Euclid’s algorithm. Extended Euclidean algorithm can be used in areas such as RSA encryption.
Algorithm principle: commonly speaking is to do division operation repeatedly with divisor and remainder, when the remainder is 0, take the current formula divisor as the largest common divisor 24 18 24%18 = 1… 6 18%6 = 3… 0 platform: Visual studio 2017 && Windows * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / 📝 implementation code 2:
#include<stdio.h>
#pragma warning(disable:4996)
int main(a)
{
int m = 0;
int n = 0;
scanf("%d%d", &m, &n);
while(m % n)
{
// Swap the dividend and divisor
int temp = m % n;
m = n;
n = temp;
}
printf("%d\n", n);
return 0;
}
Copy the code+++++++++++++++++++++++++++++++++++++++++++++++++++++++++
/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * purpose: more phase loss Strives for the greatest common divisor algorithms introduction: Jiuzhang Suanshu is an ancient Chinese mathematical monograph, in which the technique of “more phase reduction” can be used to find the greatest common divisor of two numbers. It was originally designed for divisor, but it is suitable for any occasion that requires the greatest common divisor.
Algorithm principle:
▶ Step 1: Give any two positive integers; See if they’re all even. If so, use 2 to reduce; If not, go to step 2.
▶ Step 2: Subtract the smaller number from the larger number, then compare the difference with the smaller number, and reduce the number by the larger number. Continue until the resulting subtraction and difference are equal.
▶ The product of the number of 2’s removed in step 1 and the intermediate number in step 2 is the greatest common divisor. Among them said “equal number”, is the common divisor. The method of finding “equal number” is “more phase reduction”.
Platform: Visual Studio 2017 && Windows
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
📝 implementation code 2:
#include<stdio.h>
#pragma warning(disable:4996)
int main(a)
{
int m = 0;
int n = 0;
scanf("%d%d", &m, &n);
int flag = 0;// In order to distinguish between these two numbers that have been reduced by 2
int count = 0;// Record the reduction of 2 times
int temp = 0;
while(1)
{
// Both numbers are the same
if(m == n)
{
flag = - 1;
break;
}
/ / for all
if(m % 2= =0 && n % 2= =0)
{
flag = 1;
count++;
m /= 2;
n /= 2;
}
// Not all of them
else
{
/ / big decrease
if(m > n)
{
temp = m - n;
}
else
{
temp = n - m;
}
// Compare the subtraction and difference
if(n > temp)
{
m = n;
n = temp;
}
else if(n < temp)
{
m = temp;
}
else
{
// Subtraction and difference are equal
break; }}}2 / / reduction
if(1 == flag)
{
printf("%d\n".2 * count * n);
}
// The two numbers are equal
else if(- 1 == flag)
{
printf("%d\n", m);
}
else
{
printf("%d\n", n);
}
return 0;
}
Copy the code/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * objective: optimization more phase loss A greatest common divisor algorithm principle: the above steps can be interpreted as:
▶ if m > n, then m = m-n
▶ If m < n, then n = n-m
▶ If m = n, the greatest common divisor is m
Platform: Visual Studio 2017 && Windows
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
📝 Optimization Code 2:
#include<stdio.h>
#pragma warning(disable:4996)
int main(a)
{
int m = 0;
int n = 0;
scanf("%d%d", &m, &n);
while(m ! = n) {if (m > n)
m -= n;
else
n -= m;
}
printf("%d\n", m);
return 0;
}
Copy the code+++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Comparison: The main difference between commutation and division is that the former uses “subtraction” and the latter “division”. Look from algorithm thought, there is essentially no difference between the two, but in the process of calculation, if a number is very big, the other a number of smaller, probably for a lot of times subtraction can achieve the effect of a division, degraded so as to make the algorithm’s time complexity is O (N), where N is the number of the original two larger one. In contrast, the time complexity of toss and turn division is stable at O(logN).
The friction between China and the West ends there
There are other algorithms as well
Exhaustive method: Sounds very violent
Stein algorithm: An improved algorithm based on the defect that Euclid algorithm needs test quotient to increase the operation time when it operates on large integers
/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Objective: To find the least common multiple of two input numbers.
Divide the product of two numbers by the largest common divisor.
▶ The smallest common multiple should not be less than the greater value of the two numbers, so work your way up from the greater value
Platform: Visual Studio 2017 && Windows
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
📝 implementation code 3:
#include<stdio.h>
#pragma warning(disable:4996)
int main(a)
{
int m = 0;
int n = 0;
scanf("%d%d", &m, &n);
// copy m and n
int tmp_m = m;
int tmp_n = n;
while(m ! = n) {if (m > n)
m -= n;
else
n -= m;
}
printf("%d\n", tmp_m * tmp_n / m);
return 0;
}
Copy the code📝 implementation code 4:
#include<stdio.h>
#pragma warning(disable:4996)
int main(a)
{
int m = 0;
int n = 0;
scanf("%d%d", &m, &n);
int temp = m;
while(1)
{
if(temp % m == 0 && temp % n == 0)
{
printf("%d\n", temp);
break;
}
temp++;
}
return 0;
}
Copy the code