#include <bits/stdc++.h>
#define s i*prime[j]
using namespace std;
map<int,int> mp;
map<int,bool> st;
int prime[10000001],dp[10000001];// dp[i]->当前选的是i的因数且可选,最多能选多少个数
int main(){
freopen("item.in","r",stdin);
freopen("item.out","w",stdout);
int n,pmaxn=0;
scanf("%d",&n);
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
mp[x]++;
pmaxn=max(pmaxn,x);
}
int p=0;
//筛法
for(int i=2;i<=pmaxn;i++){
if(st[i]==false){
prime[++p]=i;
}
for(int j=1;s<=pmaxn&&j<=p;j++){
st[s]=true;
if(i%prime[j]==0) break;
}
}
for(int i=1;i<=pmaxn;i++){
dp[i]+=mp[i];
for(int j=1;s<=pmaxn&&j<=p;j++){
dp[s]=max(dp[s],dp[i]);
}
}
int maxn=0;
for(int i=1;i<=pmaxn;i++){
if(mp[i]!=0){
maxn=max(maxn,dp[i]);
}
}
printf("%d",maxn);
}
/*
6
1 4 2 8 5 7
1 2 3 2 2 4
1 2 4 5 7 8
*/
DP
DP[i]表示当i为最大值的时候能够组成的最长序列
你求什么，思路吗
TLE吗？
1 个赞
求调
我来
欧拉筛+DP
你埃氏筛时间复杂度太差啦
逻辑：
欧拉筛；
输入
欧拉筛+DP
先筛吗？
对！
1 个赞
你的分解数字呢？
e，怎么写筛法，我现在这个移到前面也过不去。。。
for(int i=2;i<=10000000;i++){
if(!vis[i]){
primes[cnt++]=i;
}
for(int j=0;j<cnt&&i*primes[j]<=10000000;j++){
vis[i*primes[j]]=true;
if(i%primes[j]==0){
break;
}
}
}
用埃氏筛，晒的时候用数组统计它的最小因数
别用埃筛，太慢！
O(n log log n)应该够用
dp就行了，重构一下