Cerința

Dorel are o nouă pasiune, să coloreze divizorii unui număr natural. Primind cadou de ziua lui un număr natural n, s-a gândit să coloreze toate numerele naturale de la 1 la n cu câte o culoare, astfel încât toţi divizorii proprii ai unui număr să aibă aceeaşi culoare cu numărul. Vă roagă pe voi să aflaţi care este numărul maxim de culori care pot fi folosite.

Date de intrare

Fișierul de intrare primcolor.in conține pe prima linie numărul n.

Date de ieșire

Fișierul de ieșire primcolor.out va conține pe prima linie numărul maxim de culori ce pot fi folosite.

Restricții și precizări

• 1 ≤ n ≤ 50.000.000

Exemplu

primcolor.in

5

primcolor.out

4

Explicație

Numerele 1,2,3,4,5 pot fi colorate astfel : 1, 2,3,4,5. Se folosesc astfel 4 culori. Numerele 2 şi 4 trebuie colorate la fel deoarece 2 este divizor propriu al lui 4.

#include <bits/stdc++.h>

using namespace std;
ifstream cin("primcolor.in");
ofstream cout("primcolor.out");
bitset<50000000> ciur;
int main()
{
    for(int i = 2 ; i * i <= 50000000 ; i++)
        if(ciur[i]==0)
            for(int j = i * i; j <= 50000000; j += i) ciur[j]=1;
    int n , cnt=2;
    cin >> n;
    if(n == 1)cout << 1;
    else if(n == 2)cout << 2;
    else if(n == 3)cout << 3;
    else if(n == 4)cout << 3;
    else
    {
        for(int i = n/2 + 1 ; i <= n ; ++i)
            if(ciur[i]==0) cnt++;
        cout << cnt;
    }
    return 0;
}