Python

В компании используется генератор паролей, который создаёт пароли, состоящие из двух четырехзначных чисел,

В компании используется генератор паролей, который создаёт пароли, состоящие из двух четырехзначных чисел, расположенных следующим образом: хххх-хххх Известно, что пароль состоит из 2-х четырехзначных простых чисел. При этом последняя цифра первого числа равна первой цифре второго числа, а третья цифра первого числа равна второй цифре второго числа. Пример: хх13-31хх Для скольких сотрудников можно создать уникальные пароли?
Борис Ильин
Борис Ильин
84
В интервале [1009; 9973] - 1061 простое число. Так что сверху это ограничено миллионом с небольшим.

Получается 12583 пары.

Вот таким кодом перебираем:
 primes = [3, 5]



def test(cand):

    for n in primes:

        if n * n > cand: break

        if cand % n == 0: return False

    return True



def generate(cand, stop):

    cand |= 1

    step = (cand % 3 * 2) ^ 6

    while cand < stop:

        cand += step

        step ^= 6

        if test(cand): yield cand



def friends(n, m): # могут ли два простых числа быть двумя частями пароля

    return (m % 10 == n // 1000 % 10) and (m // 10 % 10 == n // 100 % 10)



primes += [n for n in generate(5, 100)]



highPrimes = [n for n in genPrimes(1000, 10000)]



# попарно сравниваем числа

matchingPairs = [[m, n] for n in highPrimes for m in highPrimes if friends(n, m)]



print(len(matchingPairs))
Пашка Зальцевич
Пашка Зальцевич
87 571
Лучший ответ
Пашка Зальцевич P.S. В последнем цикле получается чуть более 1 млн итераций (1061 x 1061). Можно было бы ещё отфильтровать числа, заведомо непригодные на вторую позицию, т.е. все чётные сотни (т.к. первое число никогда не будет оканчиваться на чётную цифру). Тогда удалось бы снизить количество итераций вдвое (до 1061 x 473). Ещё можно смело выкинуть диапазон 5000-5999, т.к. на 5 простые числа тоже не оканчиваются. Итого осталось бы где-то 400 тыс пробежать. И тестирование сразу в два конца (n, m) и (m, n) тоже урезало бы пробег (вместо прямоугольника пробегать "косынку") раза почти в два, тогда осталось бы 200 тыс итераций.
Борис Ильин 
 Traceback (most recent call last): 

  File "C:\Users\Lenovo\Desktop\python\43534.py", line 22, in  

    highPrimes = [n for n in genPrimes(1000, 10000)] 

NameError: name 'genPrimes' is not defined 

 

Process finished with exit code 1
В вашем коде ошибка. 
 # Банальная таблица простых чисел банальным решетом Эратосфена

t = [True] * 10000

for i in range(2, 100):

  if not t[i]: continue

  for j in range(i * i, 10000, i): t[j] = False



# Подсчёт кол-ва паролей

count = 0

for i in range(1000, 10000):

  if not t[i]: continue

  j = int(str(i)[:-3:-1]) * 100

  count += sum(t[j:j + 100])

print(count)
Akif Haciyev
Akif Haciyev
96 975
Борис Ильин При этом последняя цифра первого числа равна первой цифре второго числа, а третья цифра первого числа равна второй цифре второго числа. Пример: хх13-31хх
Борис Ильин Соответствует-ли ваша программа данному условию?
Борис Ильин Спасибо!
Дима Прохоренко Реализация генератора от Вирта на onlinegdb почти всегда быстрее. Хотя, конечно, мерять производительность на onlinegdb - та ещё рулетка. Но усреднённый замер за 10 прогонов по 10000 раз стабильно показывает выигрыш раза в полтора плюс-минус. Наверное, Эратосфен не учитывал время доступа к массиву из 10000 указателей на булеаны.
И вообще, странно, вы Эратосфеном экономите деление, а потом str(i) в цикле, где этих делений - гарантированных штук 6 на каждое число. Тогда надо было и строковые представления заранее считать и хранить.
А вот идея брать сразу диапазон, если старшие две цифры подошли, - хорошая, bisectом отрезать или при генерации складывать по диапазонам... это было бы шустро.
итого вместо восьми остаётся шесть значащих цифр
т.е. 1 000 000 вариантов
БМ
Бурхони Мирзошарив
64 673

Похожие вопросы