генерацию случайного простого числа или поиск ближайшего простого числа в заданном диапазоне.
Вот пример алгоритма для генерации случайного простого числа:
'''
Алгоритмов для создания простого чисел.
Алгоритм очень медленный, т.е проверка является ли число простым очень простое число.
'''
import time ##
#задаем количество для бит для случайного числа и потом перебираем по одному следующему числу.
bits = 50 #64 очень долго вычисляется является ли число простым?
import random
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
def generate_prime(bits):
# Генерация случайного числа с заданным числом бит
candidate = random.getrandbits(bits)
while True:
# Убедимся, что число имеет необходимое количество бит и нечетное
candidate |= (1 << bits - 1) | 1
print(candidate)
# Проверка, является ли число простым
if is_prime(candidate):
return candidate
candidate += 1
print(candidate)
#--------------------------------
start_time = time.time() ##
# Ваш код здесь ##
print("Программа начала выполнение")
random_prime = generate_prime(bits)
print(f"Случайное простое число с {bits} битами: {random_prime}")
# конец Вашего кода здесь ##
end_time = time.time() ##
elapsed_time = end_time - start_time ##
print(f"Время выполнения кода: {elapsed_time} секунд") ##
Вариант алгоритма №2 — список простых чисел.
'''
Алгоритмов для создания списка простых чисел до какогото заданного максимального числа.
'''
import time ##
#Задает начальное значение.
upper_limit = 10**3 #Надо записать результат в файл, так как при увеличении этого числа результат может не вывестить или программа зависнет.
def sieve_of_eratosthenes(limit):
sieve = [True] * (limit + 1)
sieve[0] = sieve[1] = False
for i in range(2, int(limit**0.5) + 1):
if sieve[i]:
for j in range(i*i, limit+1, i):
sieve[j] = False
primes = [num for num, is_prime in enumerate(sieve) if is_prime]
return primes
#--------------------------------
start_time = time.time() ##
# Ваш код здесь ##
print("Программа начала выполнение")
primes_up_to_100 = sieve_of_eratosthenes(upper_limit)
print(f"Простые числа до {upper_limit}: {primes_up_to_100}")
# конец Вашего кода здесь ##
end_time = time.time() ##
elapsed_time = end_time - start_time ##
print(f"Время выполнения кода: {elapsed_time} секунд") ##
Вариант алгоритма №3 — также быстрый.
В тесте простоты Миллера-Рабина параметр k обозначает количество итераций или тестов, выполняемых алгоритмом. Каждая итерация увеличивает уверенность в том, что число является простым. Чем больше итераций, тем выше вероятность правильного определения простоты числа.
В приведенном примере k=5, это означает, что алгоритм будет выполнять 5 независимых тестов для определения простоты числа. Это обычное значение для практического применения и обеспечивает достаточно высокую вероятность правильного результата.
Однако, если требуется более высокая степень уверенности, можно увеличить значение k. Например, k=10 обеспечивает более высокую степень вероятности, что число действительно простое. Но увеличение k также увеличит вычислительную нагрузку.
import random
def miller_rabin(n, k=5):
if n == 2 or n == 3:
return True
if n < 2 or n % 2 == 0:
return False
r, d = 0, n - 1
while d % 2 == 0:
r += 1
d //= 2
for _ in range(k):
a = random.randint(2, n - 2)
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
# Пример использования
test_number = 23
is_prime_test = miller_rabin(test_number)
print(f"{test_number} является простым числом: {is_prime_test}")
Алгоритм проверяет простое ли число.
'''
Несколько вариантов алгоритмов для определения простое ли число.
'''
import time ##
Число Простое Ли = 115879765459879818798794564
# Алгоритм № 1
'''
Проверка делением:
Проверьте, делится ли число на какие-либо числа от 2 до n без остатка. Если делится, то число не является простым. Этот метод обеспечивает относительно быстрое решение, особенно для небольших чисел.
'''
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
#--------------------------------
# Алгоритм № 2
'''
Тест Миллера-Рабина:
Это вероятностный тест на простоту, который предоставляет быстрое решение с высокой вероятностью. Этот метод иногда используется для больших чисел.
Выбор метода зависит от требуемой эффективности и вероятности ошибок. Тест Миллера-Рабина обеспечивает баланс между скоростью и точностью, но не является абсолютно точным.
'''
import random
def is_prime_miller_rabin(n, k=5):
if n <= 1:
return False
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False
# Представим n - 1 в виде (2^r) * d
r, d = 0, n - 1
while d % 2 == 0:
r += 1
d //= 2
# Проводим k тестов
for _ in range(k):
a = random.randint(2, n - 2)
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
#--------------------------------
print("Вариант №1 (быстро но НЕ точно.)")
start_time = time.time() ##
# Ваш код здесь ##
# Алгоритм № 2
#print(is_prime_miller_rabin(11)) # Вернет True
#print(is_prime_miller_rabin(15)) # Вернет False
print(is_prime(Число_простое_ли)) # Выдаст это число является простым или нет
# конец Вашего кода здесь ##
end_time = time.time() ##
elapsed_time = end_time - start_time ##
print(f"Время выполнения кода: {elapsed_time} секунд") ##
#--------------------------------
print("Вариант №2 (НЕ быстро, но точно.)")
start_time = time.time() ##
# Ваш код здесь ##
# Алгоритм № 1
#print(is_prime(11)) # Вернет True
#print(is_prime(15)) # Вернет False
print(is_prime(Число_простое_ли)) # Выдаст это число является простым или нет
# конец Вашего кода здесь ##
end_time = time.time() ##
elapsed_time = end_time - start_time ##
print(f"Время выполнения кода: {elapsed_time} секунд") ##
Приблизительный % чисел простых чисел в числовом ряде (т.е. в заданном диапазоне от *** до ***)
'''
import math
def prime_count_approximation(n):
return int(n / math.log(n))
# Для диапазона от 2 до 2 миллиардов. приблизительно это 7%, но если числа раступ, то процент падает и при порядке числа 30, т.е. 30*3 нулей поле 1, то процен 0.5% все равно чисел достаточно много.
lower_limit = 2
upper_limit = 2*10**9
approximate_primes = prime_count_approximation(upper_limit)
print(f"Приблизительное количество простых чисел от {lower_limit} до {upper_limit}: {approximate_primes}")
print(f"Приблизительный процент простых чисел от всего ряда в заданном диапазоне {lower_limit} до {upper_limit}: {int(approximate_primes/upper_limit*100*100)/100}%=({approximate_primes}/{upper_limit})")
'''