给定一个长度为 n 的数组，请你找到一个最长的连续区间，使得区间内数字两两之间不存在共同因子。 找到之后，输出这个最长区间的长度。

要解决这个问题，我们可以使用一种称为“埃拉托斯特尼筛法”的方法来预处理每个数的最小质因数，然后通过遍历数组来找到最长的连续区间，使得区间内数字两两之间不存在共同因子。
具体步骤如下：

预处理最小质因数：对于每个数，找到其最小的质因数。
遍历数组：使用两个指针（start 和 end）来遍历数组，找到最长的连续区间。

以下是具体的代码实现：
def longest_consecutive_range(arr):
def sieve(n):
min_prime = [0] * (n + 1)
for i in range(2, n + 1):
if min_prime[i] == 0:
min_prime[i] = i
for j in range(i * 2, n + 1, i):
if min_prime[j] == 0:
min_prime[j] = i
return min_prime

def gcd(a, b):
while b:
a, b = b, a % b
return a

min_prime = sieve(max(arr))
n = len(arr)
start, end = 0, 0
max_len = 0

for end in range(n):
for i in range(start, end):
if gcd(arr[end], arr[i]) > 1:
start = i + 1
break
max_len = max(max_len, end - start + 1)

return max_len

# 示例用法
arr = [2, 3, 5, 7, 11]
print(longest_consecutive_range(arr)) # 输出: 5
登录后复制
代码解释

**埃拉托斯特尼筛法 (sieve 函数)**：用于预处理每个数的最小质因数。
**最大公约数 (gcd 函数)**：用于计算两个数的最大公约数。
主循环：通过两个指针 start 和 end 遍历数组，找到最长的连续区间。

解释

sieve 函数生成一个数组 min_prime，其中 min_prime[i] 表示 i 的最小质因数。
gcd 函数计算两个数的最大公约数。
主循环中，start 和 end 分别表示当前区间的起始和结束位置。对于每个 end，如果 arr[end] 和 arr[i] 的最大公约数大于 1，说明这两个数有共同因子，此时将 start 更新为 i + 1，并继续寻找下一个区间。