标签：Eratosthenes筛法
You are given a list of n integers a1,...,an. You can perform the following operation: choose some ai and multiply it by any positive integer.
Your task is to compute the minimum number of different integers that could be on the list after k operations for all 0≤k≤n.
The first line of the input contains single integer n (1≤n≤3≤105). The second line of the input contains n integers ai (1≤ai≤106).
Output a single line that contains n + 1 integers. The i-th integer should be the minimum possible number of different integers in the list after i-1 operations.
6
3 4 1 2 1 2
4 4 3 3 2 2 1
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000500;
int a[maxn],n,M;
int b[maxn],ans[maxn];
int main(int argc, char const *argv[])
{
scanf("%d", &n);
for (int i = 0; i < n; ++i)
{
int x;
scanf("%d", &x);
a[x]++;
M=(x>M?x:M);
}
int cnt=0,tot=0;
for (int i = 1; i <= M; ++i)
{
if(!a[i]) continue;
tot++;
for (int j = i*2; j <= M; j+=i)
{
if(a[j]){
b[cnt++]=a[i];
break;
}
}
}
sort(b,b+cnt);
memset(ans,0x3f,sizeof ans);
int p=0,sum=0;
for (int i = 0; i <= n; ++i)
{
while(p<cnt&&sum+b[p]<=i) sum+=b[p],p++;
ans[i]=min(ans[i],tot-p);
}
cnt=0;
for (int i = 1; i <= M; ++i)
{
if(a[i]) b[cnt++]=a[i];
}
sort(b,b+cnt);
p=0,sum=0;
for (int i = 0; i <= n; ++i)
{
while(p<cnt&&sum+b[p]<=i) sum+=b[p],p++;
ans[i]=min(ans[i],tot-p+1);
printf("%d%s", ans[i],i<n?" ":"\n");
}
return 0;
}原文：https://www.cnblogs.com/sciorz/p/8968954.html