题目描述

统计从 2 到 N 各个数的质因数个数

输入格式

一个整数 N。( 2 <= N <= 1000000 )

输出格式

N-1 行，每行为对应数字的质因数个数。当对应的数字是质数时，该行输出 -1 （ 跳过 1 , 从 2 开始计算和输出，所以只有 N-1 行）。

样例

15

-1
-1
2
-1
2
-1
3
2
2
-1
3
-1
2
2

样例解释

2,3,5,7,11,13是质数，对应位置输出 -1 。 6=2*3 , 2 个质因数。 8=2*2*2 , 3 个质因数。

1. 题目分析

这条题的题意没什么玄乎的，我们学过质因数分解，知道怎么分解，也知道一个数的质因数个数怎么算（题目的意思是相同的几个质因数也考虑在内，有多少个算多少个）。

用传统的办法是可以拿到一部分分数的（如果出题人讲良心，一般能通过 60% 的测试点），问题的难点在于数据量很大。试想一下如果有一个测试点的 N 为 1000000 ， 那么就要分解接近 100 万个数，很容易超时。

1. 避免重复计算

我们设想一下，我们分解过了 45 ，分解成了 3*3*5 ， 然后再去分解 90 或者 135 的时候，好像是有一些事情做重复了，因为 90=45*2 ，我们既然分解了 45 ，知道 45 有 3 个质因数，90 是 45 的基础上乘另外一个质因数 2 得到的，90 的质因数个数就是 45 质因数个数加 1。这个关系如果不利用，重复计算就会很多。

2. 递归和递推的选择

我们以前在学 爬楼梯方案数 问题的时候既学过递归方法，也学过递推方法。在解这条题的时候，我们同样可以基于这两个思路来解题。但是，如果选用递归方法，一定要用 记忆化递归 算法。只有把算过的东西记录下来，下次找答案的时候尽量从记录查找，才能避免递归算法重复运算。

爬楼梯方案问题比较容易的是采用 递推算法，我们这个现在也重点学习 递推算法 解本题。

3. 埃氏筛法图解

累加求和问题，sum 变量要预设为 0 ；但是连乘问题，ans 变量要预设为 1 。因为 0 乘任何数都是 0 ，所以，这个 1 就相当于是一颗种子，不同的因子相乘，得到不同的数，都是从这个种子发芽长出来的。

下图为 N=40 的情况下，整个递推过程。

要点是：

1. 先找到 40 以内的所有的质数 {2,3,5,7,11,13,17,23,31,37}

2. 1 对应的格子设置成 1 （后面我们再来回顾和理解为什么要设成 1）

3. 分批次计算 40 以内的质数，整个计算过程就类似于 01背包 ， 每一个质数相当于一个物品。我们在第 i 轮考虑第 i 个物品的时候，就是从小到大过一遍表格里面填好的数字，例如 1 个质数是 2，考虑放入 2 的时候，因为 1 已经填好了数字， 1*2 = 2 ，所以，在 2 的格子上填格子 1 的数字加 1 ，然后因为 2 填好了数，所以去 2*2=4 的格子那里填 3 （因为 2 的格子是 2 ），又因为 4 填了东西，所以去 2*4=8 的格子上天 4......。只有把算过的东西记录下来，下次找答案的时候尽量从记录查找，才能避免递归算法重复运算。

4. 填格子到时候，是从一个已经填好的格子 (j) 去填另外一个没填好的格子，填数字的位置是 j*$a_i$，填上去的内容是 dp[j]+1 （$a_i$是第 i 个质数）。如果格子 j 是空的，就考虑下一个格子。

5. 当 40 以内的质数都考虑完，这个表格就会填满了数字。

上面这个方法是古希腊数学家 埃拉托斯特尼 提出的，这算法也叫 埃氏筛法==，百度词条有的，大家可以查看，增加更多数学知识。

4. 算法思路梳理

1. 格子 j ( dp[j] ) 内记录的是从 1 乘到 j，要乘多少个质因数

2. 状态转移方程 if(dp[j]) dp[ja[i]] = dp[j] + 1; 这个 if 判断很关键，如果 dp[j] 为 0 ，表示考虑到 a[i] 的时候，还没有一个方案是若干个因子相乘得到 j 的，既然没有方案乘到 j，就更没有方案撑到 ja[i]。

3. 最终，如果 j 是质数，那么 dp[j] = 2 （表示它是在 1 的基础上再乘了一个质数得到的）；只要是大于 dp[j]>2 就表明 j 是合数，j 的因子个数为 dp[j]-1

4. 从左到右填，这和 无限背包 算法类似的，所以考虑质数 2 的时候，一下子把 {2,4,8,16,32} 的格子都填了。2 相当于把物品放入了 1 次； 4 相当于放入了 2 次； 8 相当于放入了 3 次； 16 相当于放入了 4 次； 32 是放入了 5 次质因数 2 。

5. 程序填空

#include<bits/stdc++.h>
using namespace std;
int dp[1000001];
bool flag[1000001];
queue <int> q;
int main()
{
	int n,i,j,t;
	scanf("%d",&n);
		
	//找齐 2 到 n 范围内的所有质数，放入队列 q
	for(i=2;i<=n;i++)
	{
		if(!flag[i])
		{
			填空(1);
			for(j=2;i*j<=n;j++)
				flag[ 填空(2) ] = true;
		}
	}

	dp[1] = 填空(3);
	while(q.size()>0)
	{
		t = 填空(4);
		填空(5) ;
		
		for(j=1;j*t<=n;j++)
			if(填空(6))
				dp[填空(7)] = 填空(8);
	}
	
	for(i=2;i<=n;i++)
	{
		if(dp[i]==填空(9))
			printf("-1\n");
		else
			printf("%d\n",填空(10) );
	}

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}

填空(6):{{ input(6) }}

填空(7):{{ input(7) }}

填空(8):{{ input(8) }}

填空(9):{{ input(9) }}

填空(10):{{ input(10) }}