![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Решение задачи про простые числа
Задачу см. http://taki-net.livejournal.com/335594.html
Правильный ответ на первый вопрос дали почти все в разных вариациях: надо заранее посчитать любым способом (можно очень долго) простые числа до миллиона, вывести в файл, потом включить этот файл в программу в качестве начальных значений элементов массива (их около 72000), дальше организовать просмотр этого массива (хоть двоичным поиском, хоть линейно) и посчитать количество элементов этого массива, больших k и меньших n (он при этом даже не обязан быть сортированным). Вторая программа (с заранее созданным массивом) и была сдана. Кодится (не для любого компилятора) также такое решение: заранее посчитать массив от 1 до 1000000, в котором на i-м месте лежит кол-во простих чисел, меньших i. Программа состоит из одной строчки - вычитания из n-го эл-та массива k-го.
На второй вопрос - ответ под катом.
Жюри подразумевало, что участники должны реализовать решето Эратосфена "честно", не путем деления на все вообще числа меньшие корня (т.е. 1000) - это дает миллиард операций, а у нас в запасе только 200000000, и деление - дорогая операция, а путем правильно сделанного прореживания массива - удаления элементов, кратных простым числам, меньшим тысячи.
Другое возможное решение - тупым псевдоэратосфеном (деление на все до корня из верхней границы) найти все простые до 1000 - это 32000 делений и потом 1000 присваиваний, потом также тупо найти все простые до 1000000 - это около 145 млн. делений и миллион присваиваний потом. Но тут все уже зависит от "цены" деления. Может и не хватить времени.
Правильный ответ на первый вопрос дали почти все в разных вариациях: надо заранее посчитать любым способом (можно очень долго) простые числа до миллиона, вывести в файл, потом включить этот файл в программу в качестве начальных значений элементов массива (их около 72000), дальше организовать просмотр этого массива (хоть двоичным поиском, хоть линейно) и посчитать количество элементов этого массива, больших k и меньших n (он при этом даже не обязан быть сортированным). Вторая программа (с заранее созданным массивом) и была сдана. Кодится (не для любого компилятора) также такое решение: заранее посчитать массив от 1 до 1000000, в котором на i-м месте лежит кол-во простих чисел, меньших i. Программа состоит из одной строчки - вычитания из n-го эл-та массива k-го.
На второй вопрос - ответ под катом.
Жюри подразумевало, что участники должны реализовать решето Эратосфена "честно", не путем деления на все вообще числа меньшие корня (т.е. 1000) - это дает миллиард операций, а у нас в запасе только 200000000, и деление - дорогая операция, а путем правильно сделанного прореживания массива - удаления элементов, кратных простым числам, меньшим тысячи.
Другое возможное решение - тупым псевдоэратосфеном (деление на все до корня из верхней границы) найти все простые до 1000 - это 32000 делений и потом 1000 присваиваний, потом также тупо найти все простые до 1000000 - это около 145 млн. делений и миллион присваиваний потом. Но тут все уже зависит от "цены" деления. Может и не хватить времени.
no subject