Editing 2351 - Numere 23

==Cerința==
Se numește număr 3-prim, un număr natural care se poate descompune în produs de cel mult <code>3</code> numere prime, nu neapărat distincte. Cunoscând numerele naturale <code>n</code> și <code>k</code>, construiți un șir format din primele <code>n</code> numere 3-prime. Ordinea numerelor în șir va fi stabilită astfel încât, extrăgând pe rând numerele din șir, începând cu primul număr și apoi câte un număr din <code>k</code> în <code>k</code> poziții, circular, să obținem în ordine crescătoare, șirul primelor <code>n</code> numere 3-prime. Parcurgerea circulară înseamnă că după elementul aflat în vector pe locul <code>n</code>, urmează elementul de pe locul <code>1</code>.

Cunoscând numerele <code>n</code>, <code>k</code> și <code>c</code> (<code>c = 1</code> sau <code>c = 2</code>), se cere:

1. dacă <code>c = 1</code>, să se afișeze cel mai mare din cele <code>n</code> numere 3-prime.

2. dacă <code>c = 2</code>, să se construiască șirul de <code>n</code> numere care îndeplinește condiția din enunț.

==Date de intrare==
Fișierul de intrare <code>numere23.in</code> conţine pe prima linie, despărțite prin câte un spațiu, numerele naturale <code>n</code>, <code>k</code> și <code>c</code>, cu semnificaţia din enunţ.
==Date de ieșire==
Dacă <code>c = 1</code>, atunci pe prima linie a fişierului <code>numere23.out</code> va fi scris un singur număr ce reprezintă cel mai mare din cele <code>n</code> numere 3-prime. Dacă <code>c = 2</code>, atunci fişierul <code>numere23.out</code> va conţine despărțite prin câte un spațiu, șirul celor <code>n</code> numere 3-prime.
==Restricții și precizări==

* <code>0 < k < n ≤ 10000</code>

* numerotarea elementelor în vector se face de la <code>1</code>

==Exemplu 1==
;Intrare
:5  3  2
;Ieșire
:2 6 4 3 5
===Explicație===
Primele cinci numere 3-prime sunt: <code>2</code>, <code>3</code>, <code>4</code>, <code>5</code>, și <code>6</code>. Șirul de numere <code>2</code>, <code>6</code>, <code>4</code>, <code>3</code>, <code>5</code> parcurs din <code>3</code> în <code>3</code>, va forma în ordine crescătoare șirul de numere inițial.
==Exemplu 2==
;Intrare
:10 4  2
;Ieșire
:2 11 10 5 3 8 7 9 4 6
===Explicație===
Primele <code>10</code> numere 3-prime sunt: <code>2</code>, <code>3</code>, <code>4</code>, <code>5</code>, <code>6</code>, <code>7</code>, <code>8</code>, <code>9</code>, <code>10</code>, <code>11</code>. Șirul de numere <code>2</code>, <code>11</code>, <code>10</code>, <code>5</code>, <code>3</code>, <code>8</code>, <code>7</code>, <code>9</code>, <code>4</code>, <code>6</code>, parcurs din <code>4</code> în <code>4</code>, va forma în ordine crescătoare șirul de numere inițial.
==Exemplu 3==
;Intrare
:5  3  1
;Ieșire
:6
===Explicație===
Primele <code>10</code> numere 3-prime sunt: <code>2</code>, <code>3</code>, <code>4</code>, <code>5</code>, <code>6</code>, <code>7</code>, <code>8</code>, <code>9</code>, <code>10</code>, <code>11</code>. Șirul de numere <code>2</code>, <code>11</code>, <code>10</code>, <code>5</code>, <code>3</code>, <code>8</code>, <code>7</code>, <code>9</code>, <code>4</code>, <code>6</code>, parcurs din <code>4</code> în <code>4</code>, va forma în ordine crescătoare șirul de numere inițial.
==Exemplu 4==
;Intrare
:3  10  1
;Ieșire
:Date de intrare gresite!
==Rezolvare==
<syntaxhighlight lang="python" line="1">
#2351 Numere 23

def prim3(n):
    if n < 2:
        return False
    d, nr = 2, 0
    while n != 1 and nr <= 3:
        while n % d == 0 and nr <= 3:
            n //= d
            nr += 1
        d += 1
    if n == 1 and nr <= 3:
        return True

    return False


def cel_mai_mare(n):
    res = 1
    while n > 0:
        res += 1
        if prim3(res):
            n -= 1

    return res


def sir_circular(n, k):
    val, poz, nr_n = 1, 1, n
    while not prim3(val):
        val += 1
    vector = [0] * (n + 1)
    vector[1] = val
    nr_n -= 1

    while nr_n > 0:
        val += 1
        while not prim3(val):
            val += 1
        nr_k = k
        while nr_k > 0:
            poz += 1
            if poz > n:
                poz = poz % n
            if vector[poz] == 0:
                nr_k -= 1
        vector[poz] = val
        nr_n -= 1

    return " ".join(str(x) for x in v[1:])


def conditii(k, n):
    return 0 < k < n <= 10_000


def main():
    n, k, c = map(int, input().split())

    if not conditii(k, n):
        return print("Date de intrare gresite!")

    if c == 1:
        print(cel_mai_mare(n))
    elif c == 2:
        print(sir_circular(n, k))


if __name__ == "__main__":
    main()

</syntaxhighlight>