自动搬运

查看原文

来自洛谷，原作者为

	张皓涵 在洛谷，享受coding的快乐

搬运于2025-08-24 21:33:18，当前版本为作者最后更新于2018-02-01 17:50:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题主要思想是：开个数组，存质数个数，先定义为全为0，以便输出时判断，然后1、2、3...、n分别求质因子，不用判断是不是质数，因为每个质因子我们都一直除，直到不能再除，以后也不会出现可以除的数是此数的倍数了，相当于已经筛掉了，看代码吧。

#include<iostream>
using namespace std;
int a[10001]={0},n; //数组很大，记得开在外面哦
int main()
{
	cin>>n;
	for (int i=2;i<=n;i++) //1就不用了，从2到n一个一个来
	{
	 	int i2=i;  //备份一下，不然等会被除掉了
		for (int j=2;j<=i;j++)  //从2开始判断是否可以整除
			while (i2%j==0) {a[j]++; i2/=j;} 
            //记得使用while，不是if，要一除到底
	}
	for (int i=1;i<=10000;i++)  //输出
    	if (a[i]!=0)
    		cout<<i<<" "<<a[i]<<endl;
}