COCI-08 (2008) - Γύρος #2 - 2 (Reseto)

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 32M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python
Reseto

Το κόσκινο του Ερατοσθένη είναι ένας διάσημος αλγόριθμος για την εύρεση όλων των πρώτων αριθμών μέχρι το N. Ο αλγόριθμος είναι:

  1. Γράψτε όλους τους ακέραιους αριθμούς μεταξύ 2 και N, (κλειστό διάστημα [2,\;N]).
  2. Βρείτε τον μικρότερο αριθμό που δεν είναι ήδη διαγραμμένος και ονομάστε τον P. Ο P είναι πρώτος.
  3. Διαγράψτε το P και όλα τα πολλαπλάσια του που δεν έχουν ήδη διαγραφεί.
  4. Εάν δεν έχουν διαγραφεί όλοι οι αριθμοί, μεταβείτε στο βήμα 2.

Γράψτε ένα πρόγραμμα που, με δεδομένα τα N και K, να βρίσκει τον K-οστό ακέραιο προς διαγραφή.

Είσοδος

Οι ακέραιοι N και K (2 \le K < N \le 1\;000).

Έξοδος

Τυπώστε τον K-οστό ακέραιο προς διαγραφή.

Παραδείγματα

input

7 3

output

6

input

15 12

output

7

input

10 7

output

9
Επεξήγηση του 3ου παραδείγματος:

Διαγράφουμε με τη σειρά τους αριθμούς 2,\;4,\;6,\;8,\;10,\;3,\;9,\;5 και 7. Ο έβδομος αριθμός είναι το 9.


Comments

There are no comments at the moment.