На остановке N
пассажиров, среди которых были Ваня и Петя, вошли в троллейбус. Первым купил билет Ваня. Петя посмотрел на билет и увидел, что номер билета простое число и решил, что и он должен купить билет с простым номером. Есть ли шанс у Пети купить билет до следующей остановки, если у кондуктора только один рулон билетов, количество цифр в номерах билетов которого определяется купленным билетом. В случае, если рулон заканчивается и в нем нет простого номера, Петя будет ехать «зайцем» и его ждет неудача.
Входная строка содержит два числа: количество пассажиров и номер троллейбусного билета. Количество цифр в номере билета не превышает 6.
Вывести количество пассажиров, которое необходимо пропустить Пете, чтобы приобрести билет с простым номером, или -1
, если это сделать невозможно.
#include "iostream"
#include "string"
#include "math.h"
#include "sstream"
using namespace std;
int main()
{
int N, ans=-1;
bool fail=false, found=false;
long tick;
short len;
string ticket;
cin >> N >> ticket;
stringstream ss(ticket);
ss >>tick;
len=(short)ticket.length();
ticket="";
for(long i=tick+1; i < tick+N; ++i, fail=false) {
ss.str(""); ss.clear(); ss << i; ticket = ss.str();
if(len<(short)ticket.length()){ fail=true; break; }
++ans;
for(int j=2; j<=sqrt(i); ++j) {
if(!(i%j)) fail=true;
}
if(!fail) { found=true; break; }
}
cout << (fail||!found ? -1: ans) << endl;
return 0;
}
Назад
Есть решение которого нет на сайте? Пиши admin@devexe.top