Editing 2336 - primcolor


= Cerința =
Dorel are o nouă pasiune, să coloreze divizorii unui număr natural. Primind cadou de ziua lui un număr natural <code>n</code>, s-a gândit să coloreze toate numerele naturale de la <code>1</code> la <code>n</code> 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 <code>primcolor.in</code> conține pe prima linie numărul <code>n</code>.

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

= Restricții și precizări =

* <code>1 ≤ n ≤ 50.000.000</code>

= Exemplu: =
<code>primcolor.in</code>
 5
<code>primcolor.out</code>
 4

=== Explicație ===
Numerele <code>1,2,3,4,5</code> pot fi colorate astfel : 1, 2,3,4,5. Se folosesc astfel <code>4</code> culori. Numerele <code>2</code> şi <code>4</code> trebuie colorate la fel deoarece <code>2</code> este divizor propriu al lui <code>4</code>.

== Încărcare soluție ==

=== Lipește codul aici ===
1
 dim = 50000002

 f = open("primcolor.in", "r")

 g = open("primcolor.out", "w")

 v = [0] * dim

 n, m, i, j, nr, k = 0, 0, 0, 0, 0, 0

 n = int(f.readline())

 if n <= 3:

     g.write(str(n))

 else:

     m = n // 2

     v[3] = 0

     i = 3

     while i <= m:

         if v[i] == 0:

             k = i + i

             j = i + k

             while j <= n:

                 v[j] = 1

                 j = j + k

         i = i + 2

     if m % 2 == 1:

         m = m + 1

     nr = 2

     i = m + 1

     while i <= n:

         if v[i] == 0:

             nr = nr + 1

             k = i + i

             j = i + k

             while j <= n:

                 v[j] = 1

                 j = j + k

         i = i + 2

     g.write(str(nr))

 f.close()

 g.close()