Деление

[Nikita++]

Привет!!!

Есть ли какой-нибудь алгоритм, чтобы определить сколько чисел в диапазоне не делятся ни на одно из данных чисел( чисел группы )?

(Диапазон всегда от 1);

Нужно чтобы он был быстрый, так как в худшем случае таких групп чисел может быть около 30000 и в каждой группе до 800 чисел. Диапазон до 10000000 или больше. Нужно легко уложиться в 2 секунды.

Реализация или на Delphi или математически. Перебор не нужен.

Жду. Заранее спасибо!!

[danekne]

Сильно сомневаюсь. Единственное подобное, что в голову приходит - это решето Эратосфена

[Turbine]

Создаете массив булевых по величине диапазона.
Потом закрываете с шагом равным n-ному элементам группы значением true. (напр. каждый 11-й, каждый 14...)
Может так? + проверка дубляжей элементов в группах.

Булевый массив - это быстро false-true.
А основная нагрузка - найти дубляжи в группах

[Turbine]

А если есть 1, то досрочно пишем "Bingo!"

[evg_m]

Есть ли какой-нибудь алгоритм, чтобы определить сколько чисел в диапазоне не делятся ни на одно из данных чисел( чисел группы )?
(Диапазон всегда от 1);

только идея

есть число M (группа из одного числа).
узнать сколько чисел от 1 до N не делятся на M.

я правильно понял задачу (для группы из одного числа)?

представим диапазон 1..N в виде двух диапазнонов
[1..M] [M+1 ... N=M*k+r]
[1..M] [M+1..M*2]..[M*k..M*k+r]
считаем число нужных символов в каждом.

есть два числа M1 и М2
узнать с сколько чисел от 1 до N не делятся ни на M1 ни на М2.
[1..НОК(M1,M2)] ..
и далее аналогично случаю с одним числом.

[Nikita++]

Не совсем так. Но НОК и НОД не подходят - чисел слишком много. Идея с булевым массивом мне понравилась больше, но все равно дольше лимита.

[Smitt&Wesson]

Я так понимаю, эти числа заносятся не в ручную, а при помощи какого-то устройства по сбору данных?
Если так, то возникают вопросы:
- какова разрядность этого числа?
- какова скорость потока чисел?
Ответьте на них пожалуйста.

[Nikita++]

Тестирует сервер, подробностей не знаю. А зачем?

[evg_m]

переходим в систему счисления построенную на коэффициентах простых множителей.
M =2^k1 * 3^k2 * 5^k3 * .... (разложение на простые)
строим таблицу коэфф для всех чисел группы.
M1-> K1[]
M2-> K2[]
.....

1. M2 делится на M1 <=> k2[i]<=k1[i] для всех i
2. M1 делится на M2 <=> k2[i]>=K1[i] для всех i
3. M1 M2 взаимно просты <=>
есть i такое что K2[i]>K1[i] нарушено условие 1.
и есть j такое что K2[j]<K1[j] нарушено условие 2.