Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | sieve2.in, sieve2.out | Sursă | IIOT 2021-22 Runda 3 |
| Autor | Giorgio Audrito | Adăugată de |  Stefan Dascalescu •stefdascalescu |
| Timp execuţie pe test | 1 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sieve2
Giorgio is playing with the Sieve of Eratosthenes, one of the most ancient algorithms of all times. This algorithm starts with a row of all numbers from 2 to M, then repeatedly selects the smallest non-selected number remaining in the row, erasing every multiple of it. At the end of the process, only prime numbers will have survived in the row!
Giorgio is trying to apply a similar idea, but with few differences. Firstly, some numbers are missing from the starting row, which contains only N numbers overall (each of them between 2 and M), in increasing order V_0, \ldots, V_{N-1}. Secondly, every time Giorgio selects a number, he erases not only the \emph{multiples} of it but also its \emph{divisors}. As in the original algorithm, Giorgio keeps selecting numbers from the row (end erasing accordingly), stopping when every remaining number has been already selected; but he doesn't have to select numbers in increasing order. How many numbers can remain at the end of the process, at minimum?
Date de intrare
Fişierul de intrare sieve2.in ...
Date de ieşire
În fişierul de ieşire sieve2.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| sieve2.in | sieve2.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
