Cerința

Îl cunoașteți, cred, pe Cătălin, fan-ul numărul 1 al greșelilor. Ei bine, în teza la mate, Cătălin a făcut N greșeli. Presupunând, prin reducere la absurd, că el corectează o greșeală i, poate alege să corecteze o singură greșeală j, cu proprietatea 1<j<i şi i%j=0. El știe că, dacă face această alegere poate să continue din greșeala j, după aceeași regulă și nu mai poate reveni la o greșeala anterioară.

Cătălin alege T greșeli G[1] G[2] … G[T] și dorește să știe, pentru fiecare G[i], numărul maxim de greșeli pe care le poate corecta dacă începe rezolvând-o pe aceasta.

Date de intrare

Fișierul de intrare greselile.in conține pe prima linie două numere N și T unde N este numărul de greșeli și T numărul de întrebări. Următoarele T linii conțin câte un număr natural nenul reprezentând greșeala de la care Cătălin vrea să pornească corectarea.

Date de ieșire

Fișierul de ieșire greselile.out va conține fiecare linie i un singur număr natural reprezentând numărul maxim de greșeli care pot fi corectate dacă ar începe Cătălin cu greșeala G[i].

Restricții și precizări

• 1 ≤ N, T ≤ 1.000.000

Exemplu

greselile.in

10 9
3
4
6
2
5
7
8
9
10

greselile.out

1
2
2
1
1
1
3
2
2

Explicație

Corectează doar 3 deoarece numărul nu are divizori proprii.
Pornind cu 4 el va corecta 4 şi 2.
Pornind cu 6 el va corecta 6 şi 3 sau 6 și 2, maximul fiind de 2 greşeli corectate.
ș.a.m.d.

#include <bits/stdc++.h>

using namespace std;

ifstream cin("greselile.in");
ofstream cout("greselile.out");

bitset<1000001> V;
int P[1000001], nrp, D[1000001];

void eratostene(){
    V[1]=V[0]=1;
    for(int i = 2; i <= 1001; ++i)
        for(int j = 2; j * i <= 1000001; j++)
            V[j * i] = 1;
    for(int i = 1; i <= 1000001; ++i)
        if(V[i] == 0)
            P[++nrp] = i;
}

int n, t;

int desc(int n){
    int d = 1, cnt = 0;
    while(n > 1){
        int p = 0;
        while(n % P[d] == 0)
            p++, n /= P[d];
        cnt += p;
        d++;
        if(P[d] * P[d] > n && n != 1){
            cnt++;
            return cnt;
        }
    }
    return cnt;
}

int main(){
    eratostene();
    cin >> n >> t;
    for(int i = 1; i <= n; ++i)
        D[i] = desc(i);
    int x;
    for(int i = 1; i <= t; ++i)
        cin >> x , cout << D[x] << '\n';
    return 0;
}