Здравствуйте, Кодт, Вы писали:

К>Может быть, накосячил на ±1 для небольших чисел. Зуб не дам. Тестировал сразу на n>200 (потому что 11**2 = 121, т.е. прореживалка слишком быстро останавливается). Там — не лажало.

Попробуйте n=211 или n=212

К>Надо подебажить.

Там косячок для p=7 mod 12. Первые 6 остатков в xtoi Вы подправили, а в последних шести забыли.

К>Фиг знает, от чего зависит. Может, от размера кеша у конкретного процессора (у меня проц i7-4790), — всё-таки, кешмиссы там здоровенные получаются.

А, ну это полусерверные, шестиядерные, там может плохо с кэшами быть, они же для любителей.

К>Кстати о кешмиссах, — возможно, что какая-нибудь тактика группировки близких чисел либо, наоборот, раскидывания регионов, даст выигрыш.
К>Например, нашли, что p1 простое. Это значит, что все непомеченные числа в диапазоне [pi | pi <- p1..p1*p1-1, not isc[pi]] тоже простые.
К>Формируем потоки кратных [pi*(pi+ki) | ki = 0..oo]
К>они, ясное дело, бегут по диапазону [1..N] с разным темпом, поэтому реализуем слияние.

Есть такая техника, решето через приоритетную очередь (бинарный хип), в нём кипят (поднимаются и опускаются) составные числа, кратные всем простым до sqrt(N) — те самые потоки кратных. Реализована, например в проекте primes на лончпаде, генерилке простых 64-битных чисел в заданном диапазоне. В ней дорогой произвольный доступ к памяти (порядка сотни-другой тактов) меняется на логарифм количества тех простых чисел (но это в худшем случае) и на постоянно сорванный конвейер инструкций, так как при опускании в бинарном хипе все переходы непредсказуемы. И в ней Ваше прореживание по модулю (скажем, 210) могло бы ускорить вдвое как запуск, так и потоковую производительность, а заодно и требуемую память уполовинить. Можете глянуть, но там на крестах, на питоне такое делать не очень интересно.

К>Там лютый ад начинается. Я пробовал. По модулю 12 картинка очень красивая, все квадраты имеют остаток 1, и кратные вписываются всего в две схемы: +0,+4,+6,+10 и +0,+2,+6,+8.
К>По модулю 30 или 60 — количество остатков стремится к 1/4, но рисунки больно затейливые, придётся делать таблицу.

60 не надо, опять по сравнению с 30 выигрыша нет, а вот 210 может дать ещё процентов 10 (от модуля 30). А начинается не лютый ад, а как раз чёткий порядок Просто таблицы генерятся на старте самой программой, дальше лазим только по массивам. Единственное, что смущает, — основная таблица будет размера 48*48*2 байта, что с трудом лезет в L1-кэш. Если бы в ней удалось обнаружить простой порядок, можно было бы ещё упростить, но и так уже мне кажется довольно перспективным.

Update: В питоне дополнительным бонусом будет то, что шаг по массиву будет делиться на 8 или на 16 соответственно (8*x по модулю 30, 48*x по модулю 210), бесплатно получим битовые поля, ещё в 8-16 раз меньше памяти, а производительность не должна пострадать, так как маски заранее просчитаем, и сдвиги вычислим в словах.

Здравствуйте, cures, Вы писали:

C>Выброшено просеивание чётных чисел, просеивание уже просеянных маленьких чисел, и пустое просеивание по слишком большим простым числам. У меня (на идеване) для N=2400000 укладывается в 0.15 секунд, для N=24000000 — в 2 секунды, у Вас должно получиться 0.17 и 2.3 соответственно. Всё ещё не сотня, но уже чуть лучше
C>Ещё ускорить можно, если под чётные числа не выделять память, плюс переделать массив с булевого на числовой:


А еще можно на numpy сделать. Решение "в лоб" на numpy в 10 раз быстрее оптимизированного на чистом питоне, а кода меньше.

import numpy
def sieve2(n):
    prime = numpy.ones(n, dtype=numpy.bool)
    for i in range(2, int(n**0.5)+1):
        if prime[i]:
            prime[i+i::i] = False
    return list(prime.nonzero()[0][2:])

%%time
len(list(sieve2(24000000)))
CPU times: user 288 ms, sys: 84 ms, total: 372 ms
Wall time: 376 ms