выяснение делителей числа

Вот расширение на моем взятии. Сначала проверяется, есть ли возможный фактор в списке div3, Если нет, то добавляет кандидатов до число/ 2, пропуская значения, которые уже могут быть учтены в соответствии с этим списком, поэтому добавляются «37» и «43», но не «36» или «39».

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

Если список div3 Это актуально, входные данные должны быть учтены в одном из этих чисел. Если он не может, то ни один из его факторов не содержит «3». Если оно Можно, это показывает остаток, который может быть учтен далее, используя обычные методы.

Я считаю это «оптимизированным», потому что ограничение «любой фактор должен содержать« 3 »» проверяется первым. Только если любой Действительный коэффициент найден, нужно вычислить все остальные.

Моя первая программа, использующая <vector> и тому подобное, так что будьте нежны в ваших комментариях 🙂

(Правка) Теперь я заметил, что цикл проверки фактора проходит через весь div3 вектор. Конечно, нужно только подняться на number/2, Оставлено в качестве упражнения для читателя.

(Дополнительное редактирование) find3 здесь задний ход итератор. По какой-то причине это казалось уместным, но я не могу вспомнить, почему я так думал 🙂 Если проверить до и в том числе number/2, вам нужно изменить его на обычный прямой итератор.

#include <iostream>
#include <vector>

using namespace std;

int contains_3 (int value)
{
while (value && (value % 10) != 3)
value /= 10;
return value;
}

int main (int argc, char **argv)
{
int number, found_flag, last_div3, adjust, adjust_digit;
vector<int> div3;
vector<int>::reverse_iterator find3;
vector<int>::iterator it;

// a little seeding
div3.push_back(3);
div3.push_back(13);
div3.push_back(23);

if (argc != 2)
return -1;

number = atoi (argv[1]);
found_flag = 0;

// do we need to expand div3?
last_div3 = div3.back();

while (last_div3 * 2 < number)
{
//  if this number contains a '3' in any other place than the last,
//  simply increment it
if ((last_div3 % 10) != 9 && contains_3(last_div3/10))
{
last_div3++;
} else
{
// no? then simply pick the next multiple of 10 and add 3
last_div3 /= 10;
last_div3++;
last_div3 *= 10;
if (!contains_3(last_div3))
last_div3 += 3;
}
//  check if it should be in the list
for (it = div3.begin() ; it != div3.end() && (last_div3 % *it); ++it) ;
if (it == div3.end())
{
div3.push_back(last_div3);
}
}

cout << "list is now: ";
for (it = div3.begin() ; it != div3.end(); ++it)
cout << ' ' << *it;
cout << endl;

for (find3 = div3.rbegin(); !found_flag && find3 != div3.rend(); find3++)
{
if (!(number % *find3))
{
cout << "candidate: " << *find3 << ", remaining to sieve: " << number/(*find3) << endl;

found_flag++;
}
}

if (!found_flag)
cout << "None found" << endl;

return 0;
}