Решение задачи Игра Васи и Пети с Codeforces

Без пояснения   Просмотров: 106

Вася и Петя играют в одну простую игру. Вася загадал число x от 1 до n, а Петя пытается угадать это число.

Петя может задавать вопросы вида: «Делится ли загаданное число на число y?».

Игра происходит по следующим правилам: вначале Петя спрашивает все вопросы, которые его интересуют (в том числе, он может не задать ни одного вопроса), затем Вася отвечает на каждый из вопросов «да» или «нет». После получения всех ответов Петя должен назвать число, которое загадал Вася.

К сожалению, Петя не слишком хорошо разбирается в теории чисел. Помогите ему найти минимальное количество вопросов, которые он должен задать, чтобы гарантированно угадать число Васи, а также сами числа y i, про которые он должен задать вопросы.

Код 

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,r,c=0,i,t,j;
    vector<int> v;
    cin>>n;
    r=n;
    for(i=2;i<=n;i++)
    {
        t=1;
        for(j=2;j*j<=i;j++)
        if(i%j==0)
        t=0;
        r=i;
        while(t&&r<=n)
        {
            v.push_back(r);
            r*=i;
        }
    }
    cout<<v.size()<<"\n";
    for(int i:v)
    cout<<i<<" ";
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES [email protected] Карта сайта