# PBinfo #2336 – primcolor – Rezolvare C++

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

## Enunț

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.

## Cod sursă C++

```cpp
#include <fstream>
#define dim 50000002
using namespace std;
ifstream f("primcolor.in");
ofstream g("primcolor.out");
char v[dim];
int n,m,i,j,nr,k ;
int main()
{
    f >> n ;
    if ( n<=3 ) g << n ;
    else
    {
        m = n / 2 ;
        v[3] = 0 ;
        for ( i=3 ; i<=m ; i=i+2 )
            if ( v[i]==0 )
        {
            k = i + i ;
            j = i + k ;
            while ( j<=n )
            {
                v[j] = 1 ;
                j = j + k ;
            }
        }
        if ( m%2==1 ) m++ ;
        nr = 2 ;
        for ( i=m+1 ; i<=n ; i=i+2 )
            if ( v[i]==0 )
        {
            nr++ ;
            k = i + i ;
            j = i + k ;
            while ( j<=n )
            {
                v[j] = 1 ;
                j = j + k ;
            }
        }
        g << nr ;
    }
    return 0;
}
```

## Resurse

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