Разложение на множители и простые числа.
В задачах ЕГЭ по информатике часто требуется находить множители числа и проверять, является ли данное число простым. Рассмотрим способы делать это достаточно быстро.
Разложение на множители.
Самый простой способ разложения числа на множители: проверить его делимость на все числа, начиная с 2 и кончая числом, равным половине исходного. Но этот способ — слишком медленный.
Ускорить процедуру можно, если учесть тот факт, что если число n делится на число k, то оно делится и на n//k. Тогда можно проверить лишь числа от 2 до квадратного корня из n. Когда мы находим число k, на которое делится число n, то добавляем в список делителей два делителя: k и n//k. Один тонкий момент: если число n является точным квадратом числа k, то и k, и n//k — это одинаковые числа. Поэтому нужно ввести проверку и добавлять в список делителей n//k только в том случае, если это число не равно k. Тем самым мы избежим включения в массив делителей двух одинаковых чисел.
Приведем текст функции на Питоне, которая вычисляет все делители числа n, кроме единицы и самого числа n (так называемые нетривиальные делители) и возвращает массив, содержащий эти делители.
def divisors(n):
d=[]
k=2
while k*k if n%k == 0:
d.append(k)
k2 = n//k
if k2 > k: d.append(k2)
k += 1
return d
Во-первых, операция умножения выполняется гораздо быстрее, чем извлечение корня. Во-вторых, функция извлечения корня возвращает вещественный результат. А операции над вещественными числами выполняются лишь приближенно, и квадратный корень из 4 при вычислениях может оказаться равным 2.0000000001, а может и 1.9999999999. Понятно, что это может сказаться на результате сравнения самым пагубным образом.
Делители в массиве не упорядочены по возрастанию. Так, для числа 60 получается следующий результат:
Если требуется упорядоченность, то нужно либо отсортировать полученный массив, либо вставлять делители в массив, поддерживая его упорядоченность (например, с помощью функции insort из модуля bisect).
Проверка числа на простоту.
Проверка, является ли данное число простым, имеет много общего с поиском делителей. Если число простое, то оно не имеет нетривиальных делителей. Поэтому для данной цели можно использовать приведенную выше функцию: если результатом ее является пустой массив, то число простое.
Но можно написать для этой цели и отдельную функцию. Приведем её текст:
def isprime(n):
k=2
while k*k if n%k == 0: return False
k += 1
return True
Функция возвращает True, если число n — простое.
Данная функция работает несколько быстрее, чем функция divisors, т.к. она завершает работу после того, как найден первый делитель, а не ищет все делители.
Существуют и более быстрые алгоритмы для решения данных задач, но они достаточно сложны, и на ЕГЭ их не имеет смысла применять.
Нетривиальные делители числа
Здравствуйте, вот условие задачи:
Найдите числа, все нетривиальные делители которых образуют арифметическую прогрессию с шагом 12 на интервале [1200000; 1250000].
Для каждого найденного числа выведите само число и наименьший из нетривиальных делителей.
Все пары запишите в порядке возрастания найденных чисел одной строкой через пробел.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
for i in range(1200000, 1250000+1): mas = [] k = 0 sch = 0 d = 2 maxd=0 if int(i**0.5) == i**0.5: while d * d i: if i%d == 0: k += 2 mas.append(i//d) d += 1 for j in range(len(mas)-1): if mas[j+1] - mas[j] == 12: sch+=1 if sch == len(mas): print(i, mas[0]) print(m)
Не понимаю, из-за чего код выдает ошибку, а так же как сделать так чтобы код правильно работал для данных условий?
Зная простые делители числа и их количество, найти все делители числа
Добрый вечер. Есть задача: зная простые делители числа и их количество, найти все делители числа.
Даны натуральные числа p и q. Получить все делители числа q, взаимнопростые с p
как исправить, чтобы выводились только те делители, которые взаимнопросты с p? x=int(input(‘x=’)).
Делители числа
Поступает последовательность целых положительных чисел, 0 — конец последовательности. Определить.
Делители числа
Дано целое положительное число. Найдите все делители заданного числа. Вывести все делители данного.
Все делители числа
Напечатай все натуральные делители данного числа. Входные данные n — натуральное число Выходные.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
mas = [] for i in range(1200000, 1250000+1): sch = True d = 2 k = 1 mind=0 while d * d i: if i%d == 0: if mind == 0: k = 12 mind = d elif k == 12: sch = False break d += k if sch and mind: mas.extend([i, mind]) print(*mas)
Если через доказательство, что такие числа имеют всего(!) два нетривиальных делителя, то можно намного быстрее.
Простые делители числа
Здравствуйте, помогите, пожалуйста, найти все простые делители от числа 4679000 до 5000000 Там.
Найти делители числа
Найти все делители числа n. (1 < n < 100 000 000 000) Вывести надо в списке в порядке.
Простые числа и делители
Дано натуральное число P. Вывести на экран все простые числа, не превосходящие P. Посчитать их.
Четные делители, нечетные делители, простые делители, составные делители, все делители
Помогите с задачей, не как не получается сделать. Создать HTML-документ p53.html, реализующий.
Нетривиальные числа
Доброго времени суток! Помогите найти ошибку в программе и заодно оптимизировать программу. Когда.
Найдите все натуральные числа, имеющие ровно три нетривиальных делителя
Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все натуральные числа, принадлежащие отрезку [123456789; 223456789] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе его наибольший нетривиальный делитель. Ответы расположите в порядке возрастания.
for n in range (123456789, 223456790): deliteli = [] for d in range (2, n): if n % d == 0: deliteli.append(d) if len(deliteli) > 3: break if len(deliteli) == 3: print (deliteli)
Вывести все числа последовательности, имеющие ровно три делителя.
Пользователь программы вводит количество элементов последовательности и саму последовательность.
Найдите все числа, принадлежащие отрезку [a; b], имеющие ровно 6 различных делителей
Даны два натуральных числа a и b. Найдите все числа, принадлежащие отрезку , имеющие ровно 6.
Найдите все числа, принадлежащие отрезку [a; b], имеющие ровно 6 различных делителей
Даны два натуральных числа a и b. Найдите все числа, принадлежащие отрезку , имеющие ровно 6.
Найдите все числа, принадлежащие отрезку [a; b], имеющие ровно 5 различных делителей
Всем доброго времени суток, прошу помочь с решением данной задачи. Заранее огромное спасибо! .
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
def prnum(m, n) : res = set() prime = [True] * (n+1) for i in range(3, n + 1, 2) : if not prime[i]: continue if i > m: res.add(i) for j in range(i * i, n+1, i): prime[j] = False return sorted(list(res)) a = 123456789 b = 223456789 num_a = int(a**0.25) num_b = int(b**0.25) + 1 for num in prnum(num_a, num_b): print(num**4, '->', num**3)
Добавлено через 1 минуту
Три нетривиальных делителя имеют только(!) простые числа в четвертой степени
Найдите все числа, принадлежащие отрезку [a; b], имеющие ровно 6 различных делителей
Даны два натуральных числа a и b. Найдите все числа, принадлежащие отрезку , имеющие ровно 6.
Найти все числа до 10^6 имеющие ровно 3 делителя
Абраша любит число 3. А еще он любит разлагать числа на множители. Помогите Абраше найти все числа.
Найти числа имеющие ровно два различных натуральных делителя
Здравствуйте! Готовлюсь к КЕГЭ 2021 и пишу в основном на с++.Т.к все разборы задач на паскале или.
В заданном диапазоне найти числа имеющие ровно 4 различных делителя
Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку , числа.
Найдите все натуральные числа, у которых ровно пять различных нечётных делителей
Найдите все натуральные числа, принадлежащие отрезку , у которых ровно пять различных нечётных.
Найдите все натуральные числа,у которых ровно пять различных нечётных делителей
Найдите все натуральные числа, принадлежащие отрезку , у которых ровно пять различных нечётных.
2. Полезные функции и модули для эффективного решения задачи № 25 ЕГЭ
Для решения задачи \(25\) полезно уметь пользоваться \(f\)-строками — форматированными выражениями, содержащими поля замены. Форматированные \(f\)-строки имеют вид f’< текст>‘ . Поля замены ограничиваются фигурными скобками, и значения в них подставляются во время выполнения программы.
Например, фрагменты программ:
print(‘Решать задания ЕГЭ мне помогают материалы ЯКласс!’)
print(f’Решать задания ЕГЭ мне помогают материалы ЯКласс!’)
будут выполняться одинаково, хотя в верхней строке обычное форматирование, а во второй — \(f\)-строка. Обратим на это внимание в следующем примере.
Рис. \(2\). Результат работы программы \(1\)
Для аккуратного форматирования придётся воспользоваться разделителем sep\(=»\) и вставкой дополнительных пробелов в текст для того, чтобы избавиться от автоматически расставляемых пробелов на месте запятых в функции print.
Сравни результат работы с результатом работы \(f\)-строки:
Рис. \(3\). Пример вывода \(f\)-строки
Рис. \(4\). Результат работы программы \(2\)
Конечно, этим не исчерпываются возможности \(f\)-строк.
Рассмотрим задачу на поиск делителей числа.
Для некоторого случайного числа в интервале \([4,12300]\) подсчитай количество нетривиальных делителей и выведи их.
Рис. \(6\). Результат работы программы \(3\)
Обрати внимание на оформление вывода. Результаты работы программы форматированы как \(f\)-строки. В качестве объекта в фигурных скобках записана стандартная функция len от другой функции mult. Одна из этих функций составлена пользователем и описана здесь же в программе. Кроме использования вычислений в \(f\)-строке мы также можем форматировать нужные нам строки.
Даны символы «e», «c», «t», «f», «j», «k», «y». Сколько различных имён файлов, соответствующих маске \(1?23.?x?\), можно составить из предложенных символов? Сколько из них будут иметь расширение «txt» или «exe»?
Обрати внимание: для контроля за работой программы мы вывели на печать имена файлов с заданными расширениями.
Назовём маской числа последовательность цифр в которой также могут встречаться следующие символы:
символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Среди натуральных чисел, не превышающих \(10**9\), найди все числа, соответствующие маске \(12345?6?8\) и делящиеся на \(17\) без остатка.
В ответе запиши в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им частные от деления на \(17\).
Для решения задач с применением масок числа полезно знать работу функции product модуля itertools.
В условии задачи досрочного варианта упоминается, что в маске может находиться «*», а это набор символов любой длины, в том числе и нулевой.
Функция product модуля itertools сформирует нам необходимую комбинацию символов для замены «*».
Рассмотрим пример её работы.
Составь все возможные пары из элементов строк \(‘0123’\) и \(‘abcd’\) — такие, чтобы первый элемент был из числовой строки, а следующий — из текстовой. (Множество таких пар элементов называется декартовым произведением первой и второй из заданных строк.)
Мы получили список, состоящий из кортежей, первый элемент которых — из числовой строки, а второй — из текстовой.
Рис. \(12\). Результат работы программы \(6\)
Но для вставки вместо «*» нам нужно преобразовать кортежи, из которых состоит список, в строки.
Если необходимо составить комбинации пар, или троек, или иного количества символов одного множества, то необходимо задать параметр repeat для функции product.