Самый быстрый способ вычислить модуль в большом списке чисел

Я пытаюсь написать программу на С++, чтобы найти все числа с определенным диапазоном, скажем (от 1 до 3 миллиардов), которые идеально делятся на число, скажем, N. Мне было интересно, могу ли я получить указатели, чтобы сделать это максимально эффективно.

Очень простой:

for (i = 0; i < 3 BIllion; i++)
{
    if (i % N == 0) print (i);
}

Я уверен, что будут лучшие решения, так как это займет много времени. Был бы очень признателен за толчок в правильном направлении.


c++ modulus
person ababeel    schedule 28.11.2011    source источник
comment
Не уверен, насколько серьезно вы относитесь к максимально возможной эффективности или насколько практичен этот вопрос на самом деле. Может быть, лучше спросить где-нибудь, и, вероятно, на форуме Ассамблеи. Ваша первая горячая кастрюля, вероятно, является вашим печатным кодом. (мне нравится ответ Оли)   -  person Joe McGrath    schedule 28.11.2011

Ответы (1)


arrow_upward
4
arrow_downward

Вместо того, чтобы проверять все числа по очереди, почему бы просто явно не сгенерировать кратные числа?

#include <cstdint>

uint32_t i = 0;
while (i < 3000000000)
{
    printf("%d\n", i);
    i += N;
}
person Oliver Charlesworth    schedule 28.11.2011
comment
i, вероятно, должно быть целым числом без знака, так как 3 миллиарда выходит за пределы 31-битного диапазона. - person jwodder; 28.11.2011
comment
Спасибо, я делал что-то подобное. Я предполагаю, что я слишком усложнил ситуацию, думая, что я должен сделать некоторые магические манипуляции с битами, чтобы оптимизировать мод, но я думаю, что это не обязательно, поскольку компилятор все равно оптимизирует лучше, чем я. - person ababeel; 28.11.2011