因数问题——埃氏筛

• 一、算数基本定理
• • 整数的因式分解
  • 计算n的阶乘位数当中0的个数
• 二、埃氏筛

每一个大于1的整数都可以分解为若干个质数的积，切分解方式唯一

求某个数的质因子

#include
using namespace std;
#define f(elem) for(int i=0;i factor;
void All_factor(int number) {
	for (int i = 2; i * i <= number; i++) {
			if (number % i == 0) {
			while (!(number % i)) {
				factor.push_back(i), number /= i;
			}
		}
	}
	if (number > 1)factor.push_back(number);
}
int main()
{
	int number;
	cin >> number;
	factor.clear();
	All_factor(number);
	copy(factor.begin(), factor.end(), ostream_iterator(cout, " "));
}

运行结果

int  zero_cntoffac(int number) {
	int cnt = 0;
	while (number / 5 > 0) {
		cnt += number / 5;
		number /= 5;
	}
	return cnt;
}

快速判读小于等于n的质数
我们可以从2开始，将2的所有倍数标记为合数，然后找到下一个没有被标记的数，如3，将3的倍数标记为合数，最后除1以外所有没有被标记的数就是质数

void sieveofEra(int number) {
	vector v(number+1,true);
	v[1] = false;
	for(int i=2;i<=number;i++)
		if (v[i]) {
			for (int j = i*2; j <= number; j +=i)
				v[j] = false;
		}
	cout << number << "以下的所有质数为" << endl;
	for (int i = 1; i < number; i++)
		if (v[i]) cout << i << " ";
}

运行样例