基本数学问题

最大公约数

int gcd(int a,int b){
	if(b=0)return a;
	return gcd(b,a%b);
}

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

最小公倍数

a和b的最小公倍数是ab的积除他们的最大公约数：ab/d

int lcm(int a,int b){
	int d = gcd(a,b);//计算最大公约数
	return a/d*b;
}

素数/质数

素数又称质数，指除了1和自身之外，不能被其他整数整除的一类数，否则其为合数。特别注意的是1既不是素数也不是合数

素数的判断

bool isPrime(int n){
	if(n<=1)return false;
	for(int i=2;i*i<=n;i++)
		if(n%i==0) return false;
	return ture;
}

素数表的获取

//time complexity O(n根号n)
const int maxn =101;//表长
int prime[maxn],pNum=0;//prime数组存放所有素数，pNum为素数的个数
bool p[maxn]={0};
void find_prime(){
	for(int i=1;i<maxn;i++){
		if(isPrime(i)==true){
			prime[pNum++]=i;
			p[i]=true;
		}
	}
}

//埃式筛法
//time complexity O(nloglogn)
const int maxn =101;//表长
int prime[maxn],pNum=0;//prime数组存放所有素数，pNum为素数的个数
bool p[maxn]={0};//如果i为素数，p[i]为false
void find_prime(){
	for(int i=1;i<maxn;i++){
		if(p[i]==false){
			prime[pNum++]=i;
			for(int j=i+i;j<maxn;j+=i){
				//筛去所有i的倍数，循环条件不能写成j<=maxn
				p[j]=true;
			}
		}
	}
}