编程算法 - 最小能被1至n整除的数 代码(C)

最小能被1至n整除的数 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

最小能被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