| 注册
请输入搜索内容

热门搜索

Java Linux MySQL PHP JavaScript Hibernate jQuery Nginx
jopen
9年前发布

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

 本文由用户 jopen 自行上传分享,仅供网友学习交流。所有权归原作者,若您的权利被侵害,请联系管理员。
 转载本站原创文章,请注明出处,并保留原始链接、图片水印。
 本站是一个以用户分享为主的开源技术平台,欢迎各类分享!
 本文地址:https://www.open-open.com/lib/view/open1453023043433.html
C/C++开发