#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 5e6 + 10;

int n, k, g;
int a[maxn];
int f[maxn];
int h[maxn];
int p[maxn];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i], g = __gcd(a[i], g);
	int j = 0, mid = 0, q = 0;
	for (int i = 1; i <= n; i++) {
		f[i] = 1e18;
		q = (mid + 1 == i ? a[i] : __gcd(q, a[i]));
		while (j <= mid && __gcd(p[j], q) == g) ++j;
		if (j > mid) {
			mid = i, j = i + 1;
			while (j > 1 && (p[j - 1] = __gcd(p[j], a[j - 1])) > g) --j;
		}
		f[i] = min(f[i], h[j - 1] + i + k);
		if (a[i] == g) f[i] = min(f[i], f[i - 1]);
		h[i] = min(h[i - 1], f[i] - i);
	}
	cout << f[n] << endl;
	return 0;
}