def Lucas_Lehmer(p): s = xmpz(4) M = xmpz(2 ** p) - 1 startt = datetime.now() for i in range(0, p - 2): time_elapsed = datetime.now() - startt speed = i / (time_elapsed.total_seconds() + 1) remaining = (p - 2 - i) / (speed + 1) if i % int(speed + 1) == 0: print('Czas pozostały (hh:mm:ss.ms) {} czas wykonywania {}'.format(timedelta(seconds=remaining), time_elapsed)) if (s.bit_length() <= p): # Podstawowa wersja algorytmu dla s o bitach <= p s = s * s - 2 s = f_mod(s, M) else: # Optymalizacja dla s bitów > p s = s * s - 2 md = s.bit_length() % 2 right = s.bit_length() // 2 + md left = s.bit_length() // 2 s = s[0:right] + f_mod(s[left:], M)
if s == 0: return True else: return False
Zobacz też Édouard Lucas Derrick Henry Lehmer GIMPS
Uwagi
Przypisy
Linki zewnętrzne
Kategoria:Testy pierwszości