Codeforces Round 319 (Div. 1) |
---|
Закончено |
Вася и Петя играют в одну простую игру. Вася загадал число x от 1 до n, а Петя пытается угадать это число.
Петя может задавать вопросы вида: «Делится ли загаданное число на число y?».
Игра происходит по следующим правилам: вначале Петя спрашивает все вопросы, которые его интересуют (в том числе, он может не задать ни одного вопроса), затем Вася отвечает на каждый из вопросов «да» или «нет». После получения всех ответов Петя должен назвать число, которое загадал Вася.
К сожалению, Петя не слишком хорошо разбирается в теории чисел. Помогите ему найти минимальное количество вопросов, которые он должен задать, чтобы гарантированно угадать число Васи, а также сами числа yi, про которые он должен задать вопросы.
В единственной строке записано число n (1 ≤ n ≤ 103).
Выведите длину искомой последовательности вопросов k (0 ≤ k ≤ n), а затем k чисел — саму последовательность вопросов yi (1 ≤ yi ≤ n).
Если существует несколько корректных последовательностей вопросов минимальной длины, то разрешается вывести любую.
4
3
2 4 3
6
4
2 4 3 5
Последовательность из ответа на первый тест из условия действительно корректна.
Если загаданное число не делится ни на одно из чисел последовательности, то оно равно 1.
Если же загаданное число делится на 4, то оно равно 4.
Если загаданное число делится на 3, то загаданное число равно 3.
Иначе, оно равно 2. Стало быть, эта последовательность вопросов действительно угадывает загаданное число. Можно показать, что не существует последовательности вопросов состоящей из менее, чем трёх вопросов, удовлетворяющей условию.
Название |
---|