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 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.

Încărcare soluție

Lipește codul aici

​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()