編程算法 - 最小能被1至n整除的數 代碼(C)

最小能被1至n整除的數 代碼(C)

最小能被1至n整除的數, 就是1至n所有素數的乘積.

求1至n所有素數的方法, 合數最大的質數因子, 只能在sqrt(n)以內, 可以減少遍歷的范圍.

時間復雜度為O(n). O(sqrt(n)*sqrt(n)).

代碼:

/*
 * main.cpp
 *
 *  Created on: 2014.7.20
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <iostream>
#include <vector>

using namespace std;

void Primes (int n, vector<int>& vi) {
    if (n <= 2)
        return;
    bool* a = new bool[n+1];
    for (int i=1; i<=n; i++)
        a[i] = true;
    for (int i=2; i<sqrt(n); i++) {
        for (int j=2; j*i<=n; j++) {
            a[i*j] = false;
        }
    }
    for (int i=1; i<=n; ++i)
        if (a[i])
            vi.push_back(i);
    delete[] a;
}

int Division (int n) {
    vector<int> vi;
    Primes(n, vi);
    long long min = 1;
    for (size_t i=0; i<vi.size(); ++i) {
        min *= vi[i];
    }
    return min;
}

int main(void)
{
    int n = 13;
    int min = Division(n);
    cout << "min = " << min << endl;
    return 0;
}

輸出:

min = 30030

來自： http://blog.csdn.net//caroline_wendy/article/details/39432787