c/c++实现奇偶数，质数，最大公约数，最小公倍数，最大奇约数判断
c/c++实现基本数学概念转换
1.奇偶数
说明：一个整数不是奇数就是偶数，包括0，0是偶数。这里，我们可以利用一个数能被2整除则是偶数的性质，或者二进制表示该数，末位是否为1，1则是奇数的性质，可以很好判断一个数是奇是偶。
一般情况下逻辑操作比算数运算更高效。
1.1 求余判断
bool isOdd(int num)
{
return (num % 2) == 1; //奇数返回1，偶数返回0
}1.2逻辑判断
bool isOdd(int num)
{
return ( num & 1) == 1;//奇数返回1，偶数返回0
}2.质数（Prime）
（1）概念：质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数；
合数概念与之相对。
1既不是质数，也不是合数
（2）判断方法：根据合数的一个性质：若一个数是合数，那么它的最小质因数肯定小于等于其平方根。因为我们只需找到一个数存在1或者其本身以外的一个因数，我们就可以判断该数不是质数，所以可以遍历该数平方根到1之前，是否存在这个数的因数即可。
//用到函数sqrt，头文件 <math.h>
bool isPrime(int num)
{
for(int i = sqrt(mun); i>1; i--)
{
if(num%i == 0)
return 0;
}
return 1;
}//合数返回0，质数返回13.最大公约数
（1）概念：如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数。约数和倍数都表示一个整数与另一个整数的关 系，不能单独存在。如只能说16是某数的倍数，2是某数的约数，而不能孤立地说16是倍数，2是约数。最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个
（2）算法：辗转相除法，穷举法
辗转相除法
两个数相除求余，如果不为0，除数和余数继续求余，直到余数为0。直接见程序：
int getGCD(int a,int b)
{
int temp;
while(b!=0)
{
temp = a%b;
a = b;
b = temp;
}
return b;
}穷举法
设立起始一个整数i =b，如果两个数a和b能够同时整除i，那么i则为最大公约数，否则i一直递减下去。
int getGCD(int a,int b)
{
for(int i = b; i>1; i--)
{
if(a%i == 0&& b%i ==0)
return i;
}
return 1;
}4.最小公倍数
（1）概念：两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。
（2）算法：
分解质因数：先把这几个数的质因数写出来，最小公倍数等于它们所有的质因数的乘积（如果有几个质因数相同，则比较两数中哪个数有该质因数的个数较多，乘较多的次数）
公式法：由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。即（a，b）×[a，b]=a×b。所以，求两个数的最小公倍数，就可以先求出它们的最大公约数，然后用上述公式求出它们的最小公倍数。
穷举法：
int getLCM(int a,int b)
{
for(int i =b;;i++)
{
if(i%a == 0&& i%b == 0)
return i;
}
return 0;
}公式法
最小公倍数 = 两数乘积 - 最大公约数；
5.最大奇约数
奇数的最大约数是自身， 偶数的最大奇约数是除所有偶因子之后的那个奇数。所以直观的思路就是挨个遍历一遍加起来。
#include <iostream>
using namespace std;
int main(int argc, char **argv)
{
long long N;
long long sum = 0;
long long temp;
cin>>N;
for (long long i = 1; i <= N; ++i)
{
temp = i;
while(0 == temp%2)
temp /= 2;
sum += temp;
}
cout<<sum;
return 0;
}然而， N的取值范围时10^10，所以O(n)的算法是超时的。
考虑优化，设sum(i) = f(1) + f(2) + … + f(i)；
求sum(i)的过程中，如果i 为奇数可以直接求，就是 i 本身，即f(i) = i。
问题就是求所有f(i), i为偶数的和。
因为是最大奇约数，所以f(2k) = f(k)，所以f(2) + f(4) + … + f(2k) = f(1) + f(2) + … + f(k);
时间复杂度为（O（logn））
#include<iostream>
using namespace std;
long long sum(long long n) {
if (n == 1) {
return 1;
}
if (n % 2 == 0) {
return sum(n / 2) + n * n / 4;//奇数等差数列之和
}
else {
return sum(n - 1) + n;
}
}
int main() {
int N;
cin >> N;
cout << sum(N) << endl;
}转自：
[https://blog.csdn.net/FX677588/article/details/52824950]
[https://www.cnblogs.com/wangxiaobao/p/5866351.html ]