Поиск натуральные чисел, имеющих ровно 5 делителей

@dimazz33 · Регистрация: 10.08.2018

Студворк — интернет-сервис помощи студентам

Ограничение времени 1 секунда
Ограничение памяти 64Mb

Формат ввода
Программа получает на вход целое число N (N ≤ 10**9).
Формат вывода
Программа должна вывести все числа, у которых ровно пять делителей (по одному числу в строке). Гарантируется, что такие числа есть на заданном промежутке.

Есть подробное решение на Паскале, но хочется более краткое и лаконичное (+эффективность по времени и памяти) на Питоне

Для решения нужно заметить, что число будет иметь 5 делителей в том случае, когда оно является четвертой степенью простого числа. Поэтому решение задачи сводится к поиску всех простых чисел в диапазоне от 1, корень 4-ой степени из N

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
program unsimple;
var n, i, k, count, del: integer;
begin
read(n);
if n >= 16 then
  writeln(16);
k := 3;
while k * k * k * k <= n do
  begin
  count := 0;
  del := 2;
  while (count = 0) and (del * del <= k) do
      begin
      if k mod del = 0 then
        count := count + 1;
      del := del + 1;
      end;
  if count = 0 then
      writeln(k * k * k * k);
  k := k + 1;
  end;
end.

@КулХацкеръ · 29.11.2020, 18:20

Сообщение от dimazz33

Есть подробное решение на Паскале, но хочется более краткое и лаконичное

Любишь краткость и лаконизм? Я покажу тебе мощь Питона!

Python
1
list(map(lambda x:print(x**4),filter(lambda n:all([n%x for x in range(2,int(n**0.5)+1)]),range(2,int(int(input())**0.25)+1))))

@dimazz33 · 29.11.2020, 19:42 **[ТС]**

Спасибо! А можно попроще алгоритм без функций)

@Gdez · 29.11.2020, 20:54

dimazz33,

Python
1
2
3
4
5
6
7
8
9
10
n = int(input())
a = [i for i in range(178)]
a[1] = 0
i = 2
while i <= 177 and i**4 <= n :
    if a[i] != 0:
        print(i**4)
        for j in range(i, 178, i):
            a[j] = 0
    i += 1

Опережая вопрос 179^4 = 1 026 625 681 > 10^9

@КулХацкеръ · 29.11.2020, 21:23

Пара комментариев к понравившемуся мне коду от Gdez:
1)

Python
1
a = [i for i in range(178)]

Проще:

Python
1
a = list(range(178))

2)

Python
1
while i<=177 and i**4 <= n:

Проще:

Python
1
while i**4 <= n:

3)

Python
1
if a[i] != 0:

Проще:

Python
1
if a[i]:

4)

Python
1
for j in range(i, 178, i):

Быстрее:

Python
1
for j in range(i * i, 178, i):

@dimazz33 · 29.11.2020, 21:31 **[ТС]**

код супер, ещё бы краткие комментарии, цены бы не было))

@Gdez · 29.11.2020, 21:43

КулХацкеръ, каюсь

- без проверки писал "на лету"

Добавлено через 3 минуты
dimazz33, а какие комментарии то?
Весь цикл while - адаптированный алгоритм "решето Эратосфена"

@КулХацкеръ · 29.11.2020, 21:44

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#Ввод верхней границы.
n = int(input())
#Gdez использует решето Эратосфена.
#1)Инициализация булевого массива.
a = [i for i in range(178)]
#2)Число 1 - не простое.
a[1] = 0
#3)Перебор с 2 - первого простого 
#числа.
i = 2
#4)...и до последнего числа,
#биквадрат которого меньше n.
while i <= 177 and i**4 <= n :
    #Если текущее число простое...
    if a[i] != 0:
        #Выводим на печать его
        #биквадрат.
        print(i**4)
        #И вычеркиваем (отсеиваем)
        #все кратные ему числа.
        for j in range(i, 178, i):
            a[j] = 0
    #Переходим к следующему числу.
    i += 1

@dimazz33 · 29.11.2020, 21:54 **[ТС]**

ОГРОМНОЕ СПАСИБО!!!

Новые блоги и статьи Все статьи Все блоги /
10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .
Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .

@dimazz33 0 / 0 / 0 Регистрация: 10.08.2018 Сообщений: 16
	29.11.2020, 19:42 [ТС]
	Спасибо! А можно попроще алгоритм без функций) 0

@dimazz33 0 / 0 / 0 Регистрация: 10.08.2018 Сообщений: 16
	29.11.2020, 21:31 [ТС]
	код супер, ещё бы краткие комментарии, цены бы не было)) 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	29.11.2020, 21:43
	КулХацкеръ, каюсь - без проверки писал "на лету" Добавлено через 3 минуты dimazz33, а какие комментарии то? Весь цикл while - адаптированный алгоритм "решето Эратосфена" 0

@dimazz33 0 / 0 / 0 Регистрация: 10.08.2018 Сообщений: 16
	29.11.2020, 21:54 [ТС]
	ОГРОМНОЕ СПАСИБО!!! 0

Поиск натуральные чисел, имеющих ровно 5 делителей

Решение

Решение