2767 - Masterpiece 003

Cerința

Se consideră două numere naturale n și k.

Se consideră P = { p1 , p2 , p3  … pk } , șirul primelor k numere prime.

Se consideră mulțimea S = { x | x = p1e1 * p2e2 * … * pkek } unde e1 , e2 , e3  … ek sunt numere naturale.

Să se afișeze în ordine crescătoare primele n elemente mulțimii S.

Date de intrare

Programul citește de la tastatură numerele n și k.

Date de ieșire

Programul afișează pe ecran, în ordine crescătoare, separate prin câte un spațiu, primele n elemente ale mulțimii S.

Restricții și precizări

• 1 ≤ n ≤ 100000
• 1 ≤ k ≤ 10

Exemplul 1

Input:

40 5

Output:

1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32 33 35 36 40 42 44 45 48 49 50 54 55 56 60 63

Explicație:

Oricare dintre numerele afișate conțin în descompunerea lor în factori primi doar factori din mulțimea {2, 3, 5, 7, 11}.

Din șirul afișat lipsesc numerele care au în descompunerea lor în factori primi și alte numere în afară de 2, 3, 5, 7, 11. De exemplu numărul 26 nu va fi afișat pentru că, în decompunerea lui apare factorul 13.

Exemplul 2

Input:

40 99

Output:

Constrangeri neindeplinite

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verify(n, k):

   if not (1<=n<=100000):
       print("Constrangeri neindeplinite")
       exit()
   if not (1<=k<=10):
       print("Constrangeri neindeplinite")
       exit()

n, k = map(int, input().split())

verify(n,k)

s = [0] * (n + 1) p = [0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29] d = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] c = [0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

s[1] = 1

for i in range(2, n + 1):

   minim = c[1]
   for j in range(1, k + 1):
       if c[j] < minim:
           minim = c[j]
   
   s[i] = minim
   
   for j in range(1, k + 1):
       if c[j] == minim:
           d[j] += 1
           c[j] = s[d[j]] * p[j]

for i in range(1, n + 1):

   print(s[i], end=' ')

</syntaxhighlight>