Cośtam naklepałem, ale może ktoś ma lepszy pomysł? Rzecz jest
praktyczna, po prostu dwa liczniki hardwareowe pracują w kaskadzie i
każdy jest dwubajtowy, a razem są czterobajtowe, tyle że jako
iloczyn.

Czyli dla dodatniej całkowitej liczby n należy znaleźć dwie dodatnie
liczby a, b takie że n = a*b; a i b nie mogą być większe niż 0xffff,
n jest nie większe niż 0xffffffff. Jeżeli np. n jest liczbą
pierwszą, to zamiast równości mamy kryterium minimalnej abs(n - a*b).


Nota bene, stary kod w tym temacie miał proste i błędne:

a = sqrt (n);
b = n / a;

Dla n = 18 daje to 4 i 4, iloczyn 16. A można dokładnie 9 i 2, lub 3
i 6.

To co wymyśliłem to rozkład na czynniki pierwsze z nawrotami, tzn.
gdyby się nie dało to n jest zmieniane o 1. Ponieważ dla 0xffff
dobrym rozwiązaniem jest 1 i 0xffff, to dokładność 1% osiągnięta jest
dla n plus minus kilkaset. Czyli jest to wystarczające na liczby
pierwsze (tylko 2 i 3 są kolejnymi pierwszymi), a być może i niektóre
inne patologie.

Ma ktoś lepszy pomysł?

TIA