0 / 0 / 0
Регистрация: 06.09.2021
Сообщений: 5
1

Вычислить делители большого целочисленного числа

20.09.2021, 18:58. Показов 1890. Ответов 9

Author24 — интернет-сервис помощи студентам
Здравствуйте! Моя задача состоит в том, чтобы вычислить делители большого целочисленного числа. Есть код, который не получается преобразовать так, чтобы Python считывал и выводил. С меньшими числами всё работает. Что изменить?

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
25
26
27
28
29
30
31
32
33
from itertools import compress
 
def primes(n):
    """ Returns  a list of primes < n for n > 2 """
    sieve = bytearray([True]) * (n//2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = bytearray((n-i*i-1)//(2*i)+1)
    return [2,*compress(range(3,n,2), sieve[1:])]
 
def factorization(n):
    """ Returns a list of the prime factorization of n """
    pf = []
    for p in primeslist:
      if p*p > n : break
      count = 0
      while not n % p:
        n //= p
        count += 1
      if count > 0: pf.append((p, count))
    if n > 1: pf.append((n, 1))
    return pf
 
def divisors(n):
    """ Returns an unsorted list of the divisors of n """
    divs = [1]
    for p, e in factorization(n):
        divs += [x*p**k for k in range(1,e+1) for x in divs]
    return divs
 
n = 196708423
primeslist = primes(int(n**0.5)+1)
print(divisors(n))
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.09.2021, 18:58
Ответы с готовыми решениями:

Зная простые делители числа и их количество, найти все делители числа
Добрый вечер. Есть задача: зная простые делители числа и их количество, найти все делители числа....

Как найти все делители большого числа?
Мне нужно найти все делители 20! * 21! и потом среди них найти кол-во делителей, которые являются...

Вывести все одноразрядные натуральные делители произвольного большого числа
Реализовать программу , которая выводит все одноразрядные натуральные делители произвольного...

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

Четные делители, нечетные делители, простые делители, составные делители, все делители
Помогите с задачей, не как не получается сделать. Создать HTML-документ p53.html, реализующий...

9
1102 / 688 / 306
Регистрация: 05.09.2021
Сообщений: 1,193
20.09.2021, 19:07 2
Цитата Сообщение от Dukar Посмотреть сообщение
Есть код, который не получается преобразовать так, чтобы Python считывал и выводил.
Считывал и выводил что? Код запустил, что-то считает, в конце выводит список.
Цитата Сообщение от Dukar Посмотреть сообщение
С меньшими числами всё работает.
С меньшими числами какими и где? Куда их надо подставить, чтобы посмотреть изменения?
0
0 / 0 / 0
Регистрация: 06.09.2021
Сообщений: 5
20.09.2021, 19:14  [ТС] 3
Он считывает целочисленное число n (в конце кода). После считает делители этого числа. Если дописать к примеру число 19670842323423423234234234234, появится ошибка Memory Error. Мне нужно посчитать число в десятки раз больше.

Добавлено через 4 минуты
Цитата Сообщение от anton78spb Посмотреть сообщение
Считывал и выводил что? Код запустил, что-то считает, в конце выводит список.

С меньшими числами какими и где? Куда их надо подставить, чтобы посмотреть изменения?
Число изменяется в переменной n, но оно простого типа int. Требуется обработка, которая сможет считывать очень большие числа и выводить его делители в список.
0
Status 418
Эксперт Python
4577 / 2344 / 602
Регистрация: 26.11.2017
Сообщений: 5,265
Записей в блоге: 3
20.09.2021, 19:21 4
задание напишите. что нужно конкретно?
0
enx
1187 / 763 / 277
Регистрация: 05.09.2021
Сообщений: 1,772
20.09.2021, 19:25 5
Python
1
n = int(input())
ваше все, но проблема в другом,
Python
1
sieve = bytearray([True]) * (n // 2)
все равно не даст просчитать огромные числа. Как уже сказали, что вам нужно то?
0
0 / 0 / 0
Регистрация: 06.09.2021
Сообщений: 5
20.09.2021, 19:28  [ТС] 6
Цитата Сообщение от eaa Посмотреть сообщение
задание напишите. что нужно конкретно?
Задача – найти как можно больше положительных делителей заданного числа (к примеру: 61344245408094674390999497229796026032588483841393489355107324441042877125396556 78598600102235585078970471701460580534920254457589056359125409007916297366880615 2370560).
0
Status 418
Эксперт Python
4577 / 2344 / 602
Регистрация: 26.11.2017
Сообщений: 5,265
Записей в блоге: 3
20.09.2021, 19:46 7
как можно больше это сколько?
0
1102 / 688 / 306
Регистрация: 05.09.2021
Сообщений: 1,193
20.09.2021, 19:53 8
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
25
26
27
28
29
30
31
32
33
34
35
def divisors(n):
    # get factors and their counts
    factors = {}
    nn = n
    i = 2
    while i*i <= nn:
        while nn % i == 0:
            factors[i] = factors.get(i, 0) + 1
            nn //= i
        i += 1
    if nn > 1:
        factors[nn] = factors.get(nn, 0) + 1
 
    primes = list(factors.keys())
 
    # generates factors from primes[k:] subset
    def generate(k):
        if k == len(primes):
            yield 1
        else:
            rest = generate(k+1)
            prime = primes[k]
            for factor in rest:
                prime_to_i = 1
                # prime_to_i iterates prime**i values, i being all possible exponents
                for _ in range(factors[prime] + 1):
                    yield factor * prime_to_i
                    prime_to_i *= prime
 
    # in python3, 'yield from generate(0)' would also work
    for factor in generate(0):
        yield factor
 
n = 196708423
print(list(divisors(n)))
Dukar, Данный код работает гораздо быстрее вашего. Справится ли с числами необходимого вам размера точно не скажу, проверяйте.
Память вроде не жрет.
0
0 / 0 / 0
Регистрация: 06.09.2021
Сообщений: 5
20.09.2021, 21:05  [ТС] 9
Цитата Сообщение от anton78spb Посмотреть сообщение
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
25
26
27
28
29
30
31
32
33
34
35
def divisors(n):
    # get factors and their counts
    factors = {}
    nn = n
    i = 2
    while i*i <= nn:
        while nn % i == 0:
            factors[i] = factors.get(i, 0) + 1
            nn //= i
        i += 1
    if nn > 1:
        factors[nn] = factors.get(nn, 0) + 1
 
    primes = list(factors.keys())
 
    # generates factors from primes[k:] subset
    def generate(k):
        if k == len(primes):
            yield 1
        else:
            rest = generate(k+1)
            prime = primes[k]
            for factor in rest:
                prime_to_i = 1
                # prime_to_i iterates prime**i values, i being all possible exponents
                for _ in range(factors[prime] + 1):
                    yield factor * prime_to_i
                    prime_to_i *= prime
 
    # in python3, 'yield from generate(0)' would also work
    for factor in generate(0):
        yield factor
 
n = 196708423
print(list(divisors(n)))
Dukar, Данный код работает гораздо быстрее вашего. Справится ли с числами необходимого вам размера точно не скажу, проверяйте.
Память вроде не жрет.
Работает, но очень медленно. Число, в котором больше 40 цифр считает больше часа...
0
1102 / 688 / 306
Регистрация: 05.09.2021
Сообщений: 1,193
20.09.2021, 21:39 10
Dukar,
Цитата Сообщение от Dukar Посмотреть сообщение
Работает, но очень медленно. Число, в котором больше 40 цифр считает больше часа...
Вполне возможно, я такие значения не проверял.
А ваш код взятый на stackoverflow за сколько считает?

Добавлено через 13 минут
Я код который сюда кинул, тоже не сам писал. Просто было понятно, что надо использовать генераторы, чтобы память не жрало. А переделывать ваш не хотелось. Гугл выручил, по соответствующему запросу нашелся данный код. Перед тем как сюда кинуть, проверил скорость в сравнении с вашим. Этот работал на несколько порядков быстрее.

Нужна скорость, переписывайте на компилируемом языке. Алгоритм у вас есть.
0
20.09.2021, 21:39
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.09.2021, 21:39
Помогаю со студенческими работами здесь

Как вычислить факториал большого числа?
Как возвести 1000 в квадрат. Проблема заключается в том, что ни одна строка не вместит в себя число...

Даны натуральные числа р и q. Получить все делители числа q, взаимно простые с р
Очень нужна помощь.

Даны целые числа Р и Q. Получить все делители числа Q- взаимно простые с Р
Подскажите, пожалуйста, как написать код.. вот задание &quot;Даны целые числа Р и Q. Получить все...

Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p
Даны натуральные числа p и q. Получить все делители числа q , взаимно простые к p. помогите...

Найти и напечатать все простые делители заданного натурального числа числа
1)найти и напечатать все простые делители заданного натурального числа числа

Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p.
Даны натуральные числа p и q. Получить все делители числа q , взаимно простые к p.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru