//存入所有数的素数因数
//若两个数不互质，那么他们之间必然有素数因数
//dp[i][0]表示第i个数不选前i个数中能得到的最长序列
//dp[i][1]表示选了第i个数
//dp[i][0] = max(dp[i-1][0] , dp[i-1][1])
//dp[i][1] = max(dp[pos][1] + 1 ,dp[i][1] );
//pos位第i个数的质数因子出现的最后一个位置
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std ;
const int maxn = 100010 ;
int dp[maxn][2] ;
int last[maxn] ;
int a[maxn] ;
int isp[maxn] ;
int n ;
vector<int> vec[maxn] ;
void set()
{
memset(isp, 0 ,sizeof(isp)) ;
isp[1] = 1;
for(int i = 2;i < maxn ;i += 2)
{
isp[i] = 1;
vec[i].push_back(2) ;
}
for(int i = 3;i < maxn ;i++)
{
if(isp[i])continue ;
for(int j = i;j < maxn ;j+=i)
{
isp[j] = 1;
vec[j].push_back(i) ;
}
}
}
int main()
{
set() ;
while(~scanf("%d" ,&n))
{
memset(last , 0 ,sizeof(last)) ;
memset(dp , 0 ,sizeof(dp)) ;
for(int i = 1;i <= n;i++)
{
scanf("%d" ,&a[i]) ;
dp[i][0] = max(dp[i-1][0] , dp[i-1][1]);
for(int j = 0;j < vec[a[i]].size();j++)
{
int pos = last[vec[a[i]][j]] ;
dp[i][1] = max(dp[i][1] , dp[pos][1] + 1) ;
last[vec[a[i]][j]] = i;
}
}
printf("%d\n" , max(1 , max(dp[n][1] , dp[n][0]))) ;
}
return 0;
}
Codeforces Round #162 (Div. 1) B dp
原文：http://blog.csdn.net/cq_pf/article/details/45566069
