Find the number of numbers divisible by the same number?

Question

C++ / C#

Funny Game
You and your friends are playing the following game. Friends write N natural numbers on the board in a row. Your task is to find as many consecutive numbers as possible that are divisible by the same number greater than 1. Since manually searching for the answer is difficult, you decided to write a program that would do the job for you.

Specifications Input

The first line of the input contains a number N(1 ≤ N ≤ 100000). The second line contains N space-separated integers A1...AN(1 ≤ Ai ≤ 1000, 1 ≤ i ≤ N). These are the same numbers that your friends wrote. They are given in the same order as they appear on the board.

Output

Your program should print one integer — the largest number of consecutive numbers of the given sequence that would be divisible by the same natural number greater than 1.

Examples

Ввод
3
6 10 15
Вывод
2

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map> 
#include <string>
#include <math.h>
#include <deque>
using namespace std;
typedef long long ll;
ll n, x, c, ans;
vector<ll> a;
ll gcd(ll a, ll b) {
    while (b != 0) {
        a %= b;
        swap(a, b);
    }
    return a;
}
int main() {
    cin >> n;
    ans = -1;
    for (ll i = 0; i < n; i++) {
        cin >> x;
        a.push_back(x);
    }
    for (ll i = 0; i < n; i++) {
        c = a[i];
        for (ll j = i + 1; j < n;j++) {
            c = gcd(c, a[j]);
            if (c == 1) {
                ans = max(ans, j - i);
                break;
            }
        }
        if (c!=1) ans = max(ans, n-i);
    }
    cout << ans;
}

Answer 1

There are 2 solutions.
First, if you could quickly check the greatest common divisor of numbers on a segment, then you could use the two pointer method. Find the longest segment starting at the first number. Then move the left border of the segment by 1 position and move the right border greedily while you can. Here you have found the longest segment from the second position. Again move the left border by 1 and so on. Choose the maximum segment from all found.
You can quickly get the greatest common divisor for the logarithm using the segment tree data structure . The total complexity will be O(n log n).
The second solution is: Since the numbers on the segment are all divisible by something greater than 1, then they are all divisible by some prime number. So the task is to find the longest segment of numbers that are divisible by the same prime number. So you need to decompose each number in the array into prime factors and work with them separately. Further, you simply need to store for each prime factor how long the most recent segment of numbers with this divisor has and at what position it ended. When you find that the current number is divisible by p, you either need to start a new segment or add the current position to the last segment.
The total complexity of this solution will be O(n sqrt(a)), but it can be speeded up by precomputing for each number from 1 to A one of its prime divisors.