Как писать быстрые программы

[Dmitriy40]

Yadryara в сообщении #1724064 писал(а):

wrest в сообщении #1724052 писал(а):

составных остатков-частных оказалось

Вы это проверяли обычным if(!ispseudoprime(...),1)? У меня пока так делается.

Так вот, с 1 нельзя проверять составное (или простое) ли число. Потому что на некоторые составные вернёт 1 (псевдопростое).
С 1 можно проверять только если функция вернёт что оно составное, то надо предпринять какие-то действия, а если оно простое или вероятно составное/простое (и функция вернула 1 - псевдопростое) - ничего не делать. В коде так и делается, потому и можно с 1. Но это не проверка составное ли число.

--- Added ---

Грубо говоря, в коде if( ! ispseudoprime(x), <code> ) можно добавить вторым аргументом 1, но только в такого вида коде, когда нужен именно факт составного, причём ради скорости не 100% точного (не все составные выявятся, но простые точно никогда не попадут).
Без "!" или с веткой else - добавлять 1 нельзя (в смысле могут быть ошибки).

[Yadryara]

wrest в сообщении #1724089 писал(а):

Но вы писали, что никакие не делятся до 2^19-2

Извините, опять забыл уточнить, ибо я же ведь раньше уже говорил, что проверка на предпростые выполняется только один раз для каждого предпростого.

Посмотрите свою функцию, вроде она называется em3, хоть старую, хоть новую. Разве у вас не так?

И если число один раз разделилось на 163, то это учтено в частном. Но оно может и второй раз разделиться, и третий.

Это редко бывает, но бывает. И вот, чтобы проверить как работает с маленькими факторами, я нашёл один такой случай и проверил в интерпретаторе.

[wrest]

Yadryara в сообщении #1724091 писал(а):

Посмотрите свою функцию, вроде она называется em3, хоть старую, хоть новую. Разве у вас не так?

В em3 да, и это меня тяготило. Мне тут объясняли неоднократно (и вы), что надо частное считать свободным от квадратов. В последней версии, em4, опубликованной тут на 63 странице, высшие степени табличных простых у меня также проверяются post1720864.html#p1720864 :

      \\ на i-е простое разделилось d-е число цепочки
      \\ выясняем не входит ли i-е простое в более высокой степени чем 1
      ai=valuation(n0+k*m+d-1,pr[i]);
      \\ теперь ai равно степени в которой i-е простое вошло в разложение
      ns[d]*=ai+1; \\ накопили сигма-ноль

Но причём тут я? Это же вы писали, что не делится на табличные простые. Дело не в том делится или нет, а в том что вы меряете удава в попугаях, а я в слонятах или наоборот).
Но ещё раз: проверяете на "своих" числах -- дело ваше, не всем нравится сотрудничество и общий язык, понимаю!

[wrest]

Ну в общем и целом получается так, что с этими 270 числами ускорить будет весьма неспросто.
Те из них, которые легко факторизуются "кастомным" ECM, легко факторизуются и встроенным factorint(). В итоге, на "трудные" числа расходуется время как предварительного ECM так и основной факторизации и в сумме выигрыш незаметен.