б) На всякий случай: делает ли PARI\GP оптимизацию в ифах? То есть прекратит ли он считать все остатки, в случае неудачи в начале? Если нет, или нет уверенности, то это нужно делать руками.
Да, вычисления "ленивые", до первого результата, код if(x>0&&5/x>1,...) работает даже с x=0. Это сделано специально, не столько даже ради ускорения, сколько ради допустимости конструкций типа if(k>0&&v[k]>7,) если k может быть и меньше 1.
1. Надо уходить от "давайте поделим на какое-нибудь число, чтобы потом при каждой итерации на него умножать".
Теоретически да, практически смысла мало: вычисление с двумя умножениями p=p1+m*i;n=a*p-20 выполняются за 780нс, а два сложения p+=m;n+=am; выполняются за 700нс. И хотя казалось бы выигрыш более 10%, но это всего 80нс из примерно 3.2мкс на проверку у
Yadryara или порядка 2.5%. Сделать можно ибо просто, хотя эффект почти незаметен.
Отказ от вычисления p невыгоден, всё равно же придётся его вычислять, не умножением (сложением), так делением, а это точно медленнее.
Можно даже два других простых тоже вычислять сложениями, а не делениями, вот это даст бОльший эффект, хотя тоже не особо, всего 200нс выигрыш, правда это уже 6.3% от 3.2мкс.
А известно ли во сколько раз быстрее работает isprime, чем factor для чисел

?
А Вы видели что в программе уже
три цикла с factor (третий с numdiv которая тот же factor)? И Вы про какой спрашиваете, наверное про первый как самый часто запускаемый? А он выполняет не factor(), а factor(,30000), что довольно сильно отличается ибо проверяет лишь делители до 3e4 (и этим числом можно ещё и играться ради общей скорости на конкретном диапазоне чисел), зато для всех мест где они возможны и при первой же ошибке кандидат выкидывается.
Плюс и isprime() у нас с Антоном выполняется в другом виде, позволяющем отвергнуть кандидата на 10% быстрее.
И разумеется порядок проверок isprime и factor исследовался и тестировался и выбран быстрейший.
Пусть isprime быстрее работает, чем factor, в 100 раз.
isprime() намного быстрее factor() (последний в любом случае делает и isprime, как минимум для проверки последнего числа в разложении, плюс для всех найденных достаточно больших делителей). Но isprime() медленнее factor(,30000) (хотя и быстрее factor(,300000)) - и этим я с Антоном пользуемся.
Кстати, тогда уж и тройку туда же: Из остатков по модулю

живых будет

.
Тройка обычно учитывается вместе с двойкой при умножении lcm(v)*6 и коррекции p1 (тот самый +5/6*m).