Как я могу случайным образом сгенерировать число с условием, которое НЕ имеет общих факторов с двумя другими случайно сгенерированными числами

Question

p1 = 1097
p2 = 1279
p = p1*p2
phi = (p1-1)*(p1-1)

Я хочу случайным образом сгенерировать число> phi, которое не имеет общих множителей между «p» и «phi»

Answer 1

Построение чисел из известных простых чисел так, чтобы они не использовали одни и те же простые числа (как множители), должно быть быстрее, чем создание случайных чисел, их факторизация и проверка их на неперекрывающиеся множители.

Al go:

• вычислить / предоставить достаточно простых чисел для работы (которые начинаются с вашей нижней границы)
• затем создать 2 списка случайных индексов в списке простых чисел
  • первый список нарисуйте, сколько чисел вы хотите в качестве факторов
  • удалите все индексы из 2-го списка, которые уже находятся в 1-м списке, пока оба списка не подтвердят желаемое количество факторов
• затем объедините простые числа вместе

можно сделать так:

# get or calculate some primes that are big enough
# starting with 
primes = [1097,1103,1109,1117,1123,1129,1151,
  1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,
  1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,
  1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,
  1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,
  1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,
  1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,
  1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,
  1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,
  1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,
  1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,
  2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,
  2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,
  2251,2267,2269,2273,2281,2287]

затем выбрать в них индексы и умножить их, чтобы получить результат:

import random
from operator import mul
from functools import reduce

random.seed(42)
choices = random.choices

def m(numbers):
    return reduce(mul, numbers, 1)

# how many numbers to use to factorize the number you want    
size = 5

# draw f.e. 5 factors from then
p1 = [primes[i] for i in choices(range(len(primes)), k=size)]

# draw 5 others that are not in p1
p2 = []
while len(p2) != size:
  p2 = [primes[i] for i in choices(range(len(primes)), k=3 * size) if i not in p1][:size]

# calculate them 
print( m(p1), m(p2)) # 8058608274530453 8642866553052643

Выбранные вами простые числа должны быть больше, чем вдвое, чисел, которые вы хотите использовать для умножения результатов, иначе вы можете зависнуть в длительном l oop. Предоставления примерно в 5-10 раз больше простых чисел, которые вы хотите использовать в качестве факторов, должно быть достаточно.

Answer 2

Вы можете сгенерировать случайные числа, используя модуль random в python.

Чтобы обнаружить, что нет общих множителей с p и phi, вы можете проверить наибольший общий делитель (GCD) с p*phi.

from math import gcd as calcGcd
from random import randint

def getRandom(lower, upper, *noFacWithThese):
    for _ in range(upper - lower): # to avoid infinite loop
        randNum = randint(lower, upper)
        if noCommonFactors(randNum, noFacWithThese):
            return randNum
    return None

def noCommonFactors(base, withThese):
    withThis = 1
    for n in withThese: # find mutiplication of numbers inside 'withThese' list
        withThis *= n
    return calcGcd(base, withThis) == 1

p1 = 1097
p2 = 1279
p = p1*p2
phi = (p1-1)*(p1-1)

while True:
    print( getRandom(1, 10000, p, phi) )
    input()
    

Обязательно используйте необходимые нижний и верхний пределы для функции randint.

Answer 3

Не уверен, что вы имеете в виду под «не разделять общие множители между p и phi», поскольку p и phi не будут иметь общих множителей

Один из способов «грубой силы» сделать это будет запустить случайную переменную Пуассона для получения целого числа n, затем вычислить разложение каждого целого числа больше psi, пока вы не получите n-е целое число больше psi, удовлетворяющее вашему условию.

Другой способ, который я бы увидел состоит в том, чтобы взять случайное целое число больше фунта на квадратный дюйм (например, случайная переменная Пуассона) и проверить, удовлетворяют ли они вашему условию.

Зависит от того, что вы имеете в виду, и от размера ваших чисел.

РЕДАКТИРОВАТЬ: Я предлагаю переменные Пуассона, поскольку они позволяют избежать установки произвольной жестко заданной верхней границы для вашего случайного числа