编程算法 - 最小能被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