数学问题.md

公因数/公倍数

//辗转相除法,公因数
int gcd(int a,int b){
   return b==0?a:gcd(b,a%b);
}
//公倍数等于a*b/gcd(a,b)
int lcm(int a,int b){
    return a*b/gcd(a,b);
}

质数

//埃式筛法，从1，n遍历，遍历到m，则把所有小于n且是m倍数的数舍弃
int countPrimes(int n) {
        vector<bool> prime(5000010,true);
        int ans=n-2;
        if(n<=2) return 0;
        for(int i=2;i<=n;i++){
            if(prime[i]){
                for(long long j=2*i;j<n;j+=i){
                    if(prime[j]){
                        prime[j]=false;
                        --ans;
                    }
                }
            }
        }
        return ans;
}

K进制数

class Solution {
public:
    string convertToBaseK(int num,int k){
        bool is_negative=num<0;
        if(num==0) return "0";
        string ans="";
        if(is_negative) num=-num;
        while(num){
            int a=num/k,b=num%k;
            ans=to_string(b)+ans;
            num=a;
        }
        return is_negative?"-"+ans:ans;
    }
};

判断x的n次方

bool isPowerOfThree(int n,int x) {
        if(n<=0) return false;
        while(n&&n%x==0) n/=x;
        return n==1;
    }