时间复杂度 $n^2 \times \sqrt n \times \log n$
百分百超时
by __HHX__ @ 2023-06-13 20:02:06
你可以把质数判断放在输出时试试。
```cpp
for(int i=1;i<=n;i++){
if(p(j)==1 && q[i]>0){
printf("%d %d\n", i, q[i]);
}
}
```
并把前面两重循环里的判断删掉。
by lzg_070506 @ 2023-06-13 20:10:40
或者你用埃式筛筛出质数
然后枚举质数
时间复杂度 $n \log \log n + n^2 \times \log n$
by __HHX__ @ 2023-06-13 20:12:46
@[lzg_070506](/user/836138) $j$ 没了
by __HHX__ @ 2023-06-13 20:13:39
@[__HHX__](/user/717286) 改成i,不好意思
by lzg_070506 @ 2023-06-13 20:17:59
@[__HHX__](/user/717286) 对了,这是道入门题，不需要埃氏筛
by lzg_070506 @ 2023-06-13 20:19:18
@[fennudexiaozhiyin](/user/712087) 你至于吗，一道红题
```cpp
#include<iostream>
using namespace std;
int a[10001]={0},n;
int main()
{
cin>>n;
for(int i=2;i<=n;i++)
{
int i2=i;
for (int j=2;j<=i;j++)
while (i2%j==0)
{
a[j]++;
i2/=j;
}
}
for (int i=1;i<=10000;i++)
if (a[i]!=0) cout<<i<<" "<<a[i]<<endl;
return 0;
}
```
简单
by liuandwang @ 2023-06-13 20:34:23
```cpp
#include<iostream>
using namespace std;
long long a,c,d,e,v[5000000],b[5000000];
int main(){
cin>>a;
for(long long i=2;i<=a;++i){
long long h=i;
while(h!=1){
long long t=2;
while(h%t!=0)++t;
if(b[t]==0){v[c]=t;++c;b[t]=1;}
else ++b[t];
h/=t;
}
}
for(long long i=0;i<c;++i){printf("%d %d\n",v[i],b[v[i]]);}
return 0;}
```
by JasonTesla @ 2023-06-29 17:34:15
谢谢
by fennudexiaozhiyin @ 2023-08-01 13:48:57
欧拉筛
$n≤10000$
by _ikun_newperson @ 2023-08-12 14:38:18