Здравствуйте. Вот итоговый результат, который вроде как работает не хуже случайного поиска, но и не лучше.
Проверьте, пожалуйста, правильность логики кода, который созданн при участии ИИ-ассистента.
В нём идёт сравнение трёх подходов к поиску больших простых чисел:
случайный старт (рандом), детерминированная формула и гибридный вариант.
Код включает оптимизации (Smart K, wheel-sieve, быстрый отсев) и выводит статистически корректное сравнение в понятном виде.
Код в оффтопе:
(Оффтоп)
Код:
[syntax lang="python"]import random
import statistics
import math
import subprocess
import sys
# Авто-подключение gmpy2
try:
from gmpy2 import is_prime, isqrt, mpz
except ImportError:
try:
subprocess.check_call([sys.executable, "-m", "pip", "install", "gmpy2", "-q"],
stdout=subprocess.DEVNULL, stderr=subprocess.DEVNULL)
from gmpy2 import is_prime, isqrt, mpz
except Exception:
# Fallback на чистый Python, если установка не удалась
def mpz(x): return int(x)
def isqrt(n): return math.isqrt(int(n))
def is_prime(n, k=10):
n = int(n)
if n < 2: return False
if n in (2, 3): return True
if n % 2 == 0: return False
r, d = 0, n - 1
while d % 2 == 0: r += 1; d //= 2
witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] if n < 2**64 else [random.randint(2, n-2) for _ in range(k)]
for a in witnesses:
x = pow(a, d, n)
if x in (1, n-1): continue
for _ in range(r-1):
x = pow(x, 2, n)
if x == n-1: break
else: return False
return True
CONFIG = {
'N_digits': 500, # Размер чисел
'iterations': 50, # Количество тестов
'seed': 42, # Для повторяемости результатов
'max_steps': 200000, # Лимит попыток
}
PRE_FILTER = [7, 11, 13, 17, 19, 23, 29, 31]
def get_smart_structural_start(N_digits):
k = random.randint(10, 99)
for _ in range(500):
N = mpz(10)**(2 * N_digits)
m_val = isqrt(1 + k*N + (k-1)*k)
if m_val % 2 == 0: m_val += 1
if m_val % 3 != 0 and m_val % 5 != 0:
return int(m_val), k
k += 1
if k > 200: k = 10
return int(m_val), k
def find_prime_engineered(start, max_steps=200000):
curr = int(start)
if curr % 2 == 0: curr += 1
while curr % 3 == 0 or curr % 5 == 0:
curr += 2
checks = 0
wheel = [6, 4, 2, 4, 2, 4, 6, 2]
rem = curr % 30
wheel_map = {1:0, 7:1, 11:2, 13:3, 17:4, 19:5, 23:6, 29:7}
w_idx = wheel_map.get(rem, 0)
while checks < max_steps:
is_small = False
for p in PRE_FILTER:
if curr % p == 0:
is_small = True
break
if not is_small:
checks += 1
if is_prime(curr):
return checks, True
curr += wheel[w_idx]
w_idx = (w_idx + 1) % len(wheel)
return checks, False
def run_benchmark(cfg):
random.seed(cfg['seed'])
rand_res, struct_res, hybrid_res = [], [], []
N = cfg['N_digits']
for _ in range(cfg['iterations']):
s_r = random.randint(10**(N-1), 10**N - 1)
if s_r % 2 == 0: s_r += 1
c_r, _ = find_prime_engineered(s_r, cfg['max_steps'])
rand_res.append(c_r)
m_s, _ = get_smart_structural_start(N)
c_s, _ = find_prime_engineered(m_s, cfg['max_steps'])
struct_res.append(c_s)
offset = random.randint(-2000, 2000)
s_h = m_s + offset
if s_h < 10**(N-1): s_h += 4000
if s_h % 2 == 0: s_h += 1
c_h, _ = find_prime_engineered(s_h, cfg['max_steps'])
hybrid_res.append(c_h)
return rand_res, struct_res, hybrid_res
def print_results_simple(rand, struct, hybrid, N):
"""Выводит понятную таблицу с пояснениями"""
def get_stats(data):
return statistics.mean(data), statistics.stdev(data)
m_r, s_r = get_stats(rand)
m_s, s_s = get_stats(struct)
m_h, s_h = get_stats(hybrid)
n = len(rand)
print(f"\nСравнение методов поиска простых чисел ({N} цифр, {n} запусков):")
print("Число в колонке 'Среднее' — сколько раз в среднем пришлось проверить число, чтобы найти простое.")
print("Число в колонке 'Разброс' — насколько результаты отличаются друг от друга (чем меньше, тем стабильнее).")
print("-" * 95)
print(f"{'Метод поиска':<20} | {'Среднее (попыток)':>18} | {'Разброс':>10} | {'Лучший / Худший случай':>22}")
print("-" * 95)
print(f"{'Случайный старт':<20} | {m_r:>18.1f} | {s_r:>10.1f} | {min(rand):>6} / {max(rand):<6}")
print(f"{'Формула (Structural)':<20} | {m_s:>18.1f} | {s_s:>10.1f} | {min(struct):>6} / {max(struct):<6}")
print(f"{'Формула + сдвиг':<20} | {m_h:>18.1f} | {s_h:>10.1f} | {min(hybrid):>6} / {max(hybrid):<6}")
print("-" * 95)
# Простая проверка значимости
def t_test(m1, s1, m2, s2, n):
se = math.sqrt(s1**2/n + s2**2/n)
return abs(m1 - m2) / se if se > 0 else 0
t_rs = t_test(m_r, s_r, m_s, s_s, n)
t_rh = t_test(m_r, s_r, m_h, s_h, n)
best_name = "Случайный старт"
best_val = m_r
if m_s < best_val: best_name, best_val = "Формула (Structural)", m_s
if m_h < best_val: best_name, best_val = "Формула + сдвиг", m_h
print(f"\nИтог:")
if t_rs < 2.0 and t_rh < 2.0:
print("Все три метода работают примерно одинаково. Различия в цифрах — это случайность, а не закономерность.")
else:
print(f"Метод '{best_name}' показал лучший результат в среднем ({best_val:.1f} попыток), и это различие статистически значимо.")
if __name__ == "__main__":
cfg = CONFIG.copy()
if cfg['N_digits'] >= 1000:
cfg['iterations'] = 30
r, s, h = run_benchmark(cfg)
print_results_simple(r, s, h, cfg['N_digits'])[/syntax]
Полученный результат:
Код:
Сравнение методов поиска простых чисел (500 цифр, 50 запусков):
Число в колонке 'Среднее' — сколько раз в среднем пришлось проверить число, чтобы найти простое.
Число в колонке 'Разброс' — насколько результаты отличаются друг от друга (чем меньше, тем стабильнее).
-----------------------------------------------------------------------------------------------
Метод поиска | Среднее (попыток) | Разброс | Лучший / Худший случай
-----------------------------------------------------------------------------------------------
Случайный старт | 227.4 | 246.5 | 1 / 1002
Формула (Structural) | 159.1 | 202.0 | 1 / 726
Формула + сдвиг | 166.3 | 186.1 | 3 / 755
-----------------------------------------------------------------------------------------------
Итог:
Все три метода работают примерно одинаково. Различия в цифрах — это случайность, а не закономерность.
Суть метода
Алгоритм генерирует начальную точку для поиска больших простых чисел с помощью фиксированной формулы:
Формула выведена из геометрической раскладки натуральных чисел в виде трапеции и гарантирует, что при одинаковых входных параметрах (N, k) старт всегда будет одинаковым.
Ключевые оптимизации
- Smart K — автоматический подбор коэффициента k, чтобы вычисленное m гарантированно не делилось на 3 и 5.
- Колесный шаг (Wheel 2·3·5) — перебор ведётся только по числам, взаимно простым с 30, с помощью фиксированного паттерна шагов [6,4,2,4,2,4,6,2]. Исключает операции деления в цикле.
- Быстрый отсев — проверка делимости малыми простыми (7, 11, 13, …, 31) перед вызовом ресурсоёмкого теста простоты.
Эмпирические результаты:
Протестирован на числах длиной 50–1500 цифр (суммарно >500 запусков). Среднее количество вызовов is_prime статистически эквивалентно случайному поиску.
Метод не ускоряет асимптотику, но обеспечивает детерминизм, воспроизводимость и предсказуемые границы худшего случая.
