Submit solution
Points:
15 (partial)
Time limit:
1.0s
Memory limit:
32M
Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python
Reseto
Το κόσκινο του Ερατοσθένη είναι ένας διάσημος αλγόριθμος για την εύρεση όλων των πρώτων αριθμών μέχρι το . Ο αλγόριθμος είναι:
- Γράψτε όλους τους ακέραιους αριθμούς μεταξύ
και
, (κλειστό διάστημα
).
- Βρείτε τον μικρότερο αριθμό που δεν είναι ήδη διαγραμμένος και ονομάστε τον
. Ο
είναι πρώτος.
- Διαγράψτε το
και όλα τα πολλαπλάσια του που δεν έχουν ήδη διαγραφεί.
- Εάν δεν έχουν διαγραφεί όλοι οι αριθμοί, μεταβείτε στο βήμα 2.
Γράψτε ένα πρόγραμμα που, με δεδομένα τα και
, να βρίσκει τον
-οστό ακέραιο προς διαγραφή.
Είσοδος
Οι ακέραιοι και
.
Έξοδος
Τυπώστε τον -οστό ακέραιο προς διαγραφή.
Παραδείγματα
input
7 3
output
6
input
15 12
output
7
input
10 7
output
9
Επεξήγηση του 3ου παραδείγματος:
Διαγράφουμε με τη σειρά τους αριθμούς και
. Ο έβδομος αριθμός είναι το
.
Comments