# PBinfo #3273 – cmmdcsecv – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Fie un șir a1, a2, …, an de numere naturale. O secvență a șirului este o succesiune de elemente alăturate din șir, deci de forma ai, ai+1, …, aj. Lungimea acestei secvențe este dată de numărul de elemente ale secvenței, adică j – i + 1.

Cerința
Să se determine o secvență de lungime maximă din șir cu proprietatea că cel mai mare divizor comun al numerelor din secvență este strict mai mare decât 1.

Date de intrare
Fișierul de intrare cmmdcsecv.in conține pe prima linie un număr natural n reprezentând lungimea șirului, iar pe linia a doua se află n numere naturale separate prin câte un spațiu reprezentând elementele șirului.

Date de ieșire
Fișierul de ieșire cmmdcsecv.out va conține un singur număr natural reprezentând lungimea maximă a unei secvențe care are cel mai mare divizor comun strict mai mare decât 1.

Restricții și precizări

3 ≤ n ≤ 100.000
1 ≤ ai ≤ 1000, pentru orice 1 ≤ i ≤ n

Exemplu:
cmmdcsecv.in

6
15 28 14 56 42 5
cmmdcsecv.out

4
Explicație
Secvența de lungime 4 este 28 14 56 42, deoarece cmmdc(28, 14, 56, 42) = 14 > 1. Nu există în șir o secvență de lungime mai mare care să îndeplinească cerința.

## Cod sursă C++

```cpp
/*
   Implementare : prof. Dan Pracsiu
*/
#include<fstream>
using namespace std ;
int prime[200], a[100001], n, k, maxL ;
void Ciur()
{
	int i, j ;
	for(i=4; i<=1000 ; i+=2)
		a[i] = 1 ;
	k = 0 ;
	prime[k++] = 2;
	for (i = 3 ; i <= 1000 ; i++)
		if (a[i] == 0)
		{
			prime[k++] = i;
			for (j=i*i ; j <= 1000 ; j = j + 2*i)
				a[j] = 1 ;
		}
}
void Citire()
{
	ifstream fin("cmmdcsecv.in") ;
	fin >> n ;
	for (int i = 0 ; i < n ; i++)
		fin >> a[i] ;
	fin.close(); 
}
int Calcul(int x)
{
	int i, lung, lungmax ;
	lungmax = 0 ;
	i = 0 ;
	while (i < n)
		if (a[i] % x != 0) i++ ;
		else
		{
			i++ ;
			lung = 1 ;
			while (a[i] % x == 0 && i < n)
				{ i++ ; lung++ ; }
			if (lung > lungmax) lungmax = lung ;
		}
	return lungmax ;
}
void DetSol()
{
	int i, p ;
	maxL = 0 ;
	for (i = 0 ; i < k ; i++)
	{
		p = Calcul(prime[i]) ;
		if (maxL < p) maxL = p ;
	}
	ofstream fout("cmmdcsecv.out") ;
	fout << maxL << "\n" ;
	fout.close() ;
}
int main()
{
	Ciur() ;
	Citire() ;
	DetSol() ;
	return 0 ;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3273)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3273/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3273/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)