Конкретнее. Что значит не запускается? Не компилируется? Падает с ошибкой сразу после запуска? Винда говорит, что откомпилированный файл невозможно запустить?
mayton2019, Решето тоже элементарно учитывает четные и делящиеся на 3.
Но да, наивный брутфорс более прост. Но он медленнее. Хотя в этом диапазоне за десяток секунд отработает.
А решето - за пол секунды.
Позже сегодня сделаю бенчмарк, но можно и на пальцах посчитать.
Там 3400 простых. Поверю вам наслово, что в интересующем промежутке 4.5млн простых. Тогда получается 4.5млн*3400 = 15.3 млрд делений. И это не оптимизируется никакими пропусками четных. Это только вычисления, чтобы доказать, что простые - простые.
В решете же будет 3400 делений/умножений, чтобы найти первое делящееся в промежутке, и ~3* 100 млн сложений (log log 32000 * длина промежутка), чтобы проскакать по таблице помечая делящееся. Уже получается в 40 раз меньше более простых операций.
Но решето будет бегать по 12.5mb памяти. Все равно - на порядок быстрее, ибо x40 - хороший запас производительности.
Ну и последнее, автор явно про решето спрашивает же.
Ну фиг знает, как вам ответить. Они высокоуровневые? Да, наверное. Вы там не посылаете устройству USB команды, не ловите прерывания. С другой стороны, это встроенные в Windows библиотеки. Часть WinAPI. Что-то менее выскокуровневое - это уже дравйвера устройств получаются. Все остальные библиотеки - обертки над этими.
mayton2019, Для оставшихся 100000000 чисел решето будет быстрее, чем каждое число проверять на делимость всех известных.
В решете будет N/3 +N/5+N/7+... < N (log log N) операций. (N - длина отрезка)
В наивной проверке всех чисел на делители у вас будет как минимум N/logN * (sqrt(N)/log(sqrt(N)) операций - ведь для каждого простого числа в ответе придется, таки, проверить все найденные простые из списка. Это ассимптотически растет сильно быстрее оценки для решета.
Только нужны простые числа не от 2 до 500000000, а от 3 до sqrt(1000000000). Во-первых, тут алгоритм уже рассматривает только нечетные числа. Во-вторых, любое состовное число имеет простой делитель не больше его корня, поэтому не надо рассматривать простые больше sqrt(1000000000).
Их можно найти отдельным решетом или другим алгоритмом.
Slavon7, На всякий случай: вы в курсе, что на экране координаты идут из левого верхнего угла?
Этим может объяснятся, что как вы ожидаете и как у вас получилось отличаются отражением по вертикали.
Это вроде как сами что-то попытались сделать, а на самом деле нашли какой-то случайный код вообще к другой задаче, но на всякий случай, вдруг прокатит, решили вставить его в ответ?
Eka19, Надо рекурсивно пытаться приложить доминошку горизонтально и вертикально, если можно, к самой левой из самых верних непокрытых пока клеток. Запускаться рекурсивно в каждом из двух вариантов. Если по входу в функцию все поле покрыто - вы нашли решение. Надо поддерживать или глобальные переменные с текущим состоянием поля, или передавать их рекурсивно. Если где-то приложить доминошку нельзя ни горизонтально ни вертикально, то выходите из функции. Это называется backtracking.
mayton2019, Ну это же Си. И тем более человек его явно еще только учит. Так что выкручивать всякие парадигмы, подходы и абстракции - не самая лучшая идея в этом вопросе. Тут чем проще код, тем лучше, по-моему.
Проще же тупо обращаться к (i-1)-ому элементу. Отсюда кстати понятнее, почему цикл надо с 1 гнать, а не с 0. И граничные условия проверять не надо. Если массив из 1 элемента, то цикл не выполнится ни разу.
int is_ordered(int* array, int size) {
for(int i = 1; i < size; i++) {
if (array[i] < array[i-1]) return FALSE;
}
return TRUE;
}
Во-первых, у вас цикл неверный. надо left < right-2. Вы внимательно прочитали мой ответ?
Во-вторых, в конце проверяйте, а что там за элемент в left+1. Если он меньше prefix или начинается с него, то надо выдавать phrases.Count.
