Cerința
Se dau n numere naturale. Pentru fiecare număr k dat, să se afle cea mai lungă secvenţă de numere naturale consecutive din şirul 1,2,3,...,k, astfel încât orice număr din secvenţă să nu fie prim.
Date de intrare
Fișierul de intrare prim997.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.
Date de ieșire
Fișierul de ieșire prim997.out va conține pe linia i, primul număr din secvenţă şi lungimea secvenţei, pentru cel de-al i-lea număr de pe linia a doua a fişierului de intrare.
Restricții și precizări
1 ≤ n ≤ 100.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 10.000.000
dacă sunt mai multe secvenţe de lungime maximă cu numere consecutive neprime, se va afişa cea cu primul număr din secvenţă minim
Exemplu
prim997.in
3
4 11 30
prim997.out
1 1
8 3
24 5
Explicație
În şirul 1,2,3,4 secvenţa de lungime maximă cu numere neprime este 1, în şirul 1,2,3,4,5,6,7,8,9,10,11 secvenţa este 8,9,10, iar în şirul 1,2,3,4,...,30 este 24,25,26,27,28.
Răspunsuri la întrebare
Algoritmul de primalitate nu este cel eficient. Optimizarea o poti face tu.
//----------------------------//
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("prim997.in");
ofstream fout("prim997.out");
bool isPrim(int x) {
if(x==1) return false;
if(x==2 || x==3) return true;
for(int i=2; i<=x/2; i++)
if(x%i==0) return false;
return true;
}
int main()
{
int n,x,contor=0,m=0,c,cmax;
fin>>n;
while(n--) {
fin>>x;
for(int i=1; i<=x; i++) {
if(!isPrim(i)) {
if(contor==0) c=i;
contor++;
if(contor>m) {
m=contor;
cmax=c;
}
}
else contor=0;
}
fout<<cmax<<' '<<m<<endl;
}
return 0;
}