c++ - 如何检查 vector 中的整数重复？

Question

所以我正在尝试做欧拉计划中的第 5 题，它是这样写的:2520 是可以除以从 1 到 10 的每个数字而没有余数的最小数字。

能被 1 到 20 的所有数字整除的最小正数是多少？我首先尝试计算数字 1-10，然后我将移动到 1-20。这是我的代码:

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

std::vector <int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

bool isPrime(unsigned int num)
{
    if (num <= 2)
        return true;

    if ((num % 2) == 0)
        return false;

    unsigned sqr = (unsigned)sqrt(num);
    for (unsigned i = 3; i <= sqr; i += 2) {
        if (num % i == 0)
            return false;
    }

    return true;
}

void LowestMultiple(vector<int> nums) {
    for (vector< int>::iterator it = nums.begin(); it != nums.end(); it++) {
        if (isPrime(*it)) {
            cout << *it << endl;
        }
        else {
            int m = *it;
            int minit = *it;
            std::vector<unsigned int> pfactors;
            if (m % 2 == 0) {
                do {
                    m /= 2;
                } while (m % 2 == 0);
                pfactors.push_back(2);
            }

            for (int i = 3; i <= m; i += 2) {
                if (m % i == 0 && isPrime(i)) {
                    do {
                        m /= i;
                    } while (m % i == 0);
                    pfactors.push_back(i);
                }
            }
            for (vector<unsigned  int>::iterator it2 = pfactors.begin(); it2 !=       pfactors.end(); it2++) {
                cout << minit << ":" << *it2 << endl;
            }
        }
    }


}

int main() {
    LowestMultiple(nums);

    cin.get();
    return 0;
}

我创建了一个 vector ，其中包含数字 1-10 的所有质因数，现在我需要找出每个质因数在 vector 中重复了多少次，然后将这些质因数乘以相应的次数，以便得到LCM。我怎样才能做到这一点？有没有更有效的算法来解决这个问题？

Answer 1

题目的结果是[1,10]的LCM

LCM of 2 numbers lcm(a,b) = (a*b)/GCD(a,b) where GCD = Greatest Common Divisor

typedef long long ll;

ll gcd(ll a,ll b){
    if(!b)
        return a;
    else return gcd(b,a%b);
}

int main(){

    ll ans  = 1,N= 10;

    for(ll i = 2;i < N; ++i)
        ans = (ans * i)/gcd(ans,i);

    cout<<ans<<"\n";        
}