Разложение на простые

@maniac0192 · Регистрация: 27.11.2011

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

Дано натуральное число N1. Выведите все его простые натуральные делители с учетом кратности. Алгоритм должен иметь сложность O(n^1/2) .
Где- то ошибка:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def IsPrime(n):
    for i in range(2,int(n ** 0.5)+1):
        if n % i == 0:
            return False
    return True
 
a = input()
i = 2
while i < a+1:
    ch1 = i
    while IsPrime(ch1) == True and a % ch1 == 0:
        a /= ch1
        print ch1
    i += 1

@AciD · 24.11.2012, 12:26

Python
1
2
3
4
5
6
res=[]
a=int(input())
for i in range(2,int(a**0.5)+2,1):
  if IsPrime(i)==1 and a%i==0:
  res.append(i)
print(res)

@maniac0192 · 24.11.2012, 13:34 **[ТС]**

вот пример, по которому это должно работать 132 - 2 2 3 11, по данному так не получается

@AciD · 24.11.2012, 14:51

Наверное вы что-то перепутали, потому что быстрого и эффективного разложения на простые множители в природе не существует... (я не прав?)

@maniac0192 · 24.11.2012, 16:13 **[ТС]**

в задание я написал, с учётом кратности, вы не находите?

@AciD · 25.11.2012, 04:37

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def IsPrime(n):
    for i in range(2,int(n ** 0.5)+1):
        if n % i == 0:
            return False
    return True
a=int(input())
res=[]
i=2
while IsPrime(a)==0:
    if IsPrime(i)==1 and a%i==0:
        a=int(a/i)
        res.append(i)
        i=2
    i+=1
res.append(a)
print(sorted(res))

accept · 26.11.2012, 02:00

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

Где- то ошибка:

надо прибавлять по два
3 5 7 9 ...
а двойку проверять отдельно

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@maniac0192 17 / 17 / 5 Регистрация: 27.11.2011 Сообщений: 141
	24.11.2012, 13:34 [ТС]
	вот пример, по которому это должно работать 132 - 2 2 3 11, по данному так не получается 0

@AciD 22 / 22 / 19 Регистрация: 25.10.2011 Сообщений: 122
	24.11.2012, 14:51
	Наверное вы что-то перепутали, потому что быстрого и эффективного разложения на простые множители в природе не существует... (я не прав?) 1

@maniac0192 17 / 17 / 5 Регистрация: 27.11.2011 Сообщений: 141
	24.11.2012, 16:13 [ТС]
	в задание я написал, с учётом кратности, вы не находите? 0