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
Το κόσκινο του Ερατοσθένη είναι ένας διάσημος αλγόριθμος για την εύρεση όλων των πρώτων αριθμών μέχρι το . Ο αλγόριθμος είναι:
- Γράψτε όλους τους ακέραιους αριθμούς μεταξύ και , (κλειστό διάστημα ). 
- Βρείτε τον μικρότερο αριθμό που δεν είναι ήδη διαγραμμένος και ονομάστε τον . Ο είναι πρώτος. 
- Διαγράψτε το και όλα τα πολλαπλάσια του που δεν έχουν ήδη διαγραφεί. 
- Εάν δεν έχουν διαγραφεί όλοι οι αριθμοί, μεταβείτε στο βήμα 2.
Γράψτε ένα πρόγραμμα που, με δεδομένα τα  και 
, να βρίσκει τον 
-οστό ακέραιο προς διαγραφή.
Είσοδος
Οι ακέραιοι  και 
.
Έξοδος
Τυπώστε τον -οστό ακέραιο προς διαγραφή.
Παραδείγματα
input
7 3output
6input
15 12output
7input
10 7output
9Επεξήγηση του 3ου παραδείγματος:
Διαγράφουμε με τη σειρά τους αριθμούς  και 
. Ο έβδομος αριθμός είναι το 
.
Comments