素数问题

1.辗转相除法

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

gcd函数用于求两数的最大公约数，该函数递归的返回a，b中较小的数和他们相除之后的余数。直到两数除尽，此时a即为最大公约数。
例如给定平面上两个格点P1，P2，线段P1P2上除P1和P2还有多少个格点。
此题用辗转相除法可以高效的解决，实际上就是求|x1-x2|和|y1-y2|的最大公约数。

2.素性测试

素数即为恰好只有两个因数的整数，即1与它自身，由于n的约数都不超过n，所以只需检查2~n-1是否为素数即可。
并且，若p为n的约数，那么n/p也为n的因数。由于<，所以只需检查2~的数即可，时间复杂度为o()
例题：统计所有小于非负整数 n 的质数的数量。

   bool is_prime(int x){
        for(int i=2;i*i<=x;i++){
            if(x%i==0)
                return false;
        }
        return true;
    }
    
    int countPrimes(int n) {
        if(n==1)
            return 0;
        int count=0;
        for(int i=2;i<n;i++){
            if(is_prime(i)){
                count++;
            }
        }
        return count;
    }

但是这样的算法显然不够高效，有一个更加高效的埃氏筛法
将2到n内的所有整数列出来，其中最小的数为2将所有2和2的倍数删去，然后最小的数为3，再把3的倍数删去......依次类推。反复操作之后就能枚举出所有的素数。
埃氏筛法的时间复杂度是

    int countPrimes(int n) {
        if(n==1||n==0)
            return 0;
        int count=0;
        vector<bool> is_prime(n,true);
        is_prime[0]=is_prime[1]=false;
        for(int i=2;i<n;i++){
            if(is_prime[i]==true){
                count++;
                for(int j=i*2;j<n;j+=i){
                    is_prime[j]=false;
                }
            }
        }
        return count;
    }

其实埃氏筛法还有可以改进的地方，由于每一个合数可以看成多个质因数相乘，所以一个合数可能被筛多次，如12的可以看作223，所以它既会被2筛掉也会被3筛掉。这里我们引入了欧拉筛法，可以保证每个合数只会被它最小的质因数筛。

int countPrimes(int n) {
        if(n==1||n==0)
            return 0;
        int count=0;
        vector<bool> is_prime(n,true);
        vector<int> ola(n);
        is_prime[0]=is_prime[1]=false;
        for(int i=2;i<n;i++){
            if(is_prime[i]==true)
                ola[count++]=i;
            for(int j=0;j<count&&i*ola[j]<n;j++){
                is_prime[i*ola[j]]=false;
                if(i%ola[j]==0){
                    break;
                }
            }
        }
        return count;
    }

---

leetcode263 丑数

编写一个程序判断给定的数是否为丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

class Solution {
public:
    bool isUgly(int num) {
        if(num==1)
            return true;
        if(num==0)
            return false;
        if(num%2==0)
            return isUgly(num/2);
        if(num%3==0)
            return isUgly(num/3);
        if(num%5==0)
            return isUgly(num/5);
        return false;
    }
};

---

pat 1059

#include <iostream>
#include <map>
using namespace std;

bool is_prime(int x) {
    for (int i = 2; i*i <= x; ++i) {
        if (x%i == 0)
            return true;
    }
    return false;
}

map<int,int> prime_factors(int x) {
    map<int, int> res;
    for (int i = 2; i <= x; ++i) {
        int num = 0;
        while (x%i == 0) {
            x /= i;
            ++res[i];
        }
    }
    return res;
}

int main()
{
    int x;
    cin >> x;
    if (x != 1 && is_prime(x)) {
        map<int,int> res=prime_factors(x);
        cout << x << "=";
        map<int, int>::iterator it = res.begin();
        int i = 1;
        while (i != res.size()) {
            if (it->second == 1) {
                cout << it->first << "*";
            }
            else {
                cout << it->first << "^" << it->second << "*";
            }
            i++;
            it++;
        }
        if (it->second == 1) {
            cout << it->first << endl;
        }
        else {
            cout << it->first << "^" << it->second << endl;
        }
    }
    else {
        cout << x << "=" << x << endl;
    }
    return 0;
}