题目描述

读五年级的楠楠刚学完了质数、合数、因数、质因数等概念。

他还知道了每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，叫做这个合数的质因数．把一个合数用质因数相乘的形式表示出来，叫做分解质因数。

聪明爱动脑筋的楠楠突然对具有互不相同的质因数的合数产生了兴趣。例如：30=2×3×5，它有互不相同的质因数；70=2×5×7，它也有互不相同的质因数。若一个合数中所有的质因数互不相同，则把它称之为具有单纯质因数的合数。他想知道还有哪些数是单纯质因数的合数。

你现在要帮楠楠解决的问题是：已知 N ,依次输出 N 以内所有具有单纯质因数的合数。

输入格式

输入数据只一个整数 N（ 10 <= N <= 100000 ）。

输出格式

依次输出 N 以内所有具有单纯质因数的合数。

样例

12

6 10

解题思路

这条题实际上很难的，题目并不复杂，很容易看得懂。直接想到的方法也很多，但是很容易超时。

解题的方向有 2 个，一个是分解，一个是乘。这两个方向是逆运算，一正一反。大家都可以尝试一下。

如果用分解的方法，很可能是会超时的。比方说你找到了 1000 个质数，你要分解 k 的时候，你很可能要枚举很多次才能分解完 k ，这个过程你要一个个质数去试，所以效率就比较低。用乘的思维，再结合一些其它的技巧，可以让合格过程效率提高很多。

如果用乘的思路来解这条题，那么就需要用到一个结论：一个具有单纯质因数的合数乘另一个质数会得到一个具有单纯质因数的合数。==这句话有点绕口，请大家仔细想一下是不是这样。这种数学的规律，需要考生自己在考试的时候找出来。所以，难的信息题首先难在数学。

上面结论里面，有一个地方很关键，乘另一个质数，这里的另一个是什么意思呢？例如，21=3*7，所以 21 是符合条件的合数，如果它乘 11 ，得到 231，这个数也是符合条件的合数，但是，如果你做 21*3， 得到的 63 就不是一个符合条件的数了。因为 3 已经是 21 的质因数，你乘 2 次 3 就违反约定了。

所以，我们可以想象一下，我们从 1 开始，不断的乘质数，得到的新的数字，新的数字又再乘质数，又得到新的数字。下面，我们还要解决一个问题：

1. 一个质数不能乘 2 次的问题。我们在 dfs 的时候，记录着最大的质数是什么，下一次乘运算的时候，只找更大的质数来乘。也就是说，我们是按照升序来乘质数的，这就一定可以避免一个质数乘了几次，或者是不同的顺序乘，得到的是同一个数字的问题。

2. 输出的时候判断是不是合数，可以用埃式筛选法的合数表。

反过来说，如果一个合数，本身就不是单纯

完善程序

#include<bits/stdc++.h>
using namespace std;
int prime[100001],cnt,tot,n;
int ans[100001];
bool flag[100001];
void dfs(long long a,int START) // START 为本层可以从哪一个质数开始选
{
	long long t;
	for(int i=填空(1);i<=cnt;i++)
	{
		t = a*prime[i]; // 如果 t 用 int 类型，这个地方乘出来可能会溢出，得到一个负数 
		if(填空(2))
		{
			ans[++tot]= t; // t<=n 才会运行这行，t 会自动从 long long 转成 int，而且没有数据丢失 
			dfs(填空(3),填空(4));
		}
		else 填空(5);
	}
}
int main()
{
	scanf("%d",&n);

	// 埃氏赛选法打表
	for(int i=2;i<=n;i++)
	{
		if(!flag[i])
		{
			prime[++cnt] = i;
			for(int j=2;j*i<=n;j++)
				flag[i*j]= true;
		}
	}

	dfs(填空(6),填空(7));

	//题目要求从小到大输出
	sort(ans+1,ans+1+tot);
	
	for(int i=填空(8);填空(9);i++)
		if( 填空(10)) // ans[i] 有可能是质数，需要剔除
			printf("%d ",ans[i]);

    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) }}