C++(g++ 7.5.0) 解法, 执行用时: 36ms, 内存消耗: 13184K, 提交时间: 2022-10-25 22:51:54

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+6;

int prime[N];
int visit[N];
void Eulerprime(){
	memset(visit,0,sizeof(visit));
	memset(prime,0,sizeof(prime));
	for(int i=2;i<=N;i++){
		if(!visit[i]){
			prime[++prime[0]] = i;
			visit[i] = i; 
		}
		for(int j=1; j<= prime[0] && i*prime[j] <= N;j++){
			visit[i*prime[j]] = prime[j];
			if(i% prime[j] == 0) break;
		}
	}
}

int g[N], a[N];

int main(){
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
	Eulerprime();
	for(int j = 1; j <= prime[0]; j++) g[prime[j]] = n;
    int index = a[0];
    while(index > 1){
        g[visit[index]] = 0;
        index /= visit[index];
    }
    int ans = 1;
    for(int i = 0; i < n; i++) {
        ans = i + 1;
        index = a[i];
        while(index > 1){
            ans = min(g[visit[index]] + 1, ans);
            index /= visit[index];
        }
        if(i == n - 1) break;
        index = a[i + 1];
        while(index > 1){
            g[visit[index]] = min(g[visit[index]], ans);
            index /= visit[index];
        }
    }
   	cout << ans << endl;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 42ms, 内存消耗: 10344K, 提交时间: 2020-05-10 15:24:04

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+100;
bool number[maxn];
int prime[maxn];
int dp[maxn],g[maxn];
int mnp[maxn];
int a[100005];
void init()
{
	int i,j,cnt=0;
	memset(number,true,sizeof(number));
	for(i=2;i<1e6+5;i++)
	{
		if(number[i])
			prime[++cnt]=i,mnp[i]=cnt;
		for(j=1;j<=cnt&&prime[j]*i<1e6+5;j++)
        {
            number[prime[j]*i]=false;
            mnp[i*prime[j]]=j;
            if(i%prime[j]==0)
                break;
        }
	}
}
int main()
{
	init();
	int n;
	cin>>n;
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	for(int i=1;i<maxn;i++) g[i]=n;
	for(int i=1;i<=n;i++)
	{
		int tmp=a[i-1];
		dp[i]=n;
		while(1)
		{
			if(tmp<=1) break;
			int temp=mnp[tmp];
			g[temp]=min(g[temp],dp[i-1]);
			dp[i]=min(dp[i],g[temp]+1);
			tmp/=prime[temp];
		}
	}
	printf("%d\n",dp[n]);
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 46ms, 内存消耗: 12516K, 提交时间: 2020-05-10 15:13:36

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
int fac[1000010];
int dp[1000010];
int mn[1000010];
int n,a[100010];
int main(){
	cin>>n;
	rep(i,1,n)	scanf("%d",a+i);
	rep(i,2,1000005){
		if(fac[i]==0){
			fac[i]=i;
			for(int j=2;j*i<=1000005;j++){
				fac[i*j]=max(fac[i*j],i);
			}
		}
	}
	memset(mn,0x3f,sizeof(mn));
	memset(dp,0x3f,sizeof(dp));
	mn[0]=0;
	rep(i,1,n){
		while(a[i]!=1){
			int prime=fac[a[i]];
			dp[prime]=min(mn[i-1]+1,dp[prime]);
			mn[i]=min(mn[i],dp[prime]);
			a[i]/=prime;
		}
	}
	printf("%d\n",mn[n]);
	return 0;
}