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 ===
<syntaxhighlight lang="python" line="1">
dim = 50000002
f = open("primcolorin.txt", "r")
g = open("primcolorout.txt", "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()
</syntaxhighlight>