о том и речь, что с математической точки зрения у нас есть БЕСКОНЕЧНАЯ бумажка, на которой мы пишем числа. в том и состоит (учебный, ничего особо умного, конечно - это чисто учебная задача для школьников) прикол, как эту бесконечность ЭМУЛИРОВАТЬ в вычислительном процессе
если мы тащим за собой "мешок" (словарь) уже найденных простых - то мешок неизбежно растет. конечно, можно не тащить, но это будет другая стратегия, и даже возможно другая задача.
исходная задача такая: сделайте Эратосфен (или а ля Эратосфен), но не для фиксированного интервала (а стандартный Эратосфен именно именно об этом), но чтобы найти нужное число простых чисел. дурацкая - не дурацкая, но я встретил именно такую постановку.
я за любую оптимизацию, но надо четко понимать, оптмизация ЧЕГО. самого алгоритма или его имплементации.
не эта задача ставилась. исходная задача - сделать именно и конкретно Эратосфен. но раздвижной.
с другой стороны, вы перемешали - оптимизация ЧЕГО. оптимизация кода и оптимизация алгоритма. Эратосфен не оптимален, но никто и не говорил что он оптимален.
большое спасибо, но речь была НЕ об оптимизации. это учебная задача с одной конкретной целью - обычный Эратосфен, но произвольно раздвинутый.
идея в том, чтобы не делить. делить запрещено. только что-то складывать. такое вот учебное ограничение
о том и речь, что с математической точки зрения у нас есть БЕСКОНЕЧНАЯ бумажка, на которой мы пишем числа. в том и состоит (учебный, ничего особо умного, конечно - это чисто учебная задача для школьников) прикол, как эту бесконечность ЭМУЛИРОВАТЬ в вычислительном процессе
если мы тащим за собой "мешок" (словарь) уже найденных простых - то мешок неизбежно растет. конечно, можно не тащить, но это будет другая стратегия, и даже возможно другая задача.
исходная задача такая: сделайте Эратосфен (или а ля Эратосфен), но не для фиксированного интервала (а стандартный Эратосфен именно именно об этом), но чтобы найти нужное число простых чисел. дурацкая - не дурацкая, но я встретил именно такую постановку.
я за любую оптимизацию, но надо четко понимать, оптмизация ЧЕГО. самого алгоритма или его имплементации.
речь не об оптимизации.
не эта задача ставилась. исходная задача - сделать именно и конкретно Эратосфен. но раздвижной.
с другой стороны, вы перемешали - оптимизация ЧЕГО. оптимизация кода и оптимизация алгоритма. Эратосфен не оптимален, но никто и не говорил что он оптимален.
вроде есть - 49 бардовая, как все кратные 7