Робота з великими числами

Трошки історії

У 1938 році американський математик Едвард Казнер гуляв у парку з двома своїми племінниками і обговорював з ними великі числа. В ході розмови зайшла мова про число із ста нулями, в якого не було власної назви. Один з племінників, дев’ятирічний Мілтон Сиротта, запропонував назвати це число «гугол» (googol). У 1940 році Едвард Казнер спільно з Джеймсом Ньюманом написав науково-популярну книгу «Математика і уяву», де і розповів любителям математики про число гугол.

А чи чули ви таке число, як гуголплекс?

Гуголплекс – це число з гуголом нулів після одиниці.

Якщо надрукувати гуголплекс у книжках, кожна з яких буде містити мільйон знаків (400 сторінок, 50 рядків на сторінках, 50 знаків у рядку), то знадобиться 10 в 94 степені таких книг. Якщо кожна книжка буде важити 100 граммів, то їхня загальна маса складе 10 в 93 степені кілограми. Наприклад, маса Землі становить 5,972 х 10^24 кілограмів, а маса Чумацького шляху - 6 x 10^42 кілограмів.

Написати це число в звичайній, десятковій, системі числення неможливо, навіть якщо всю матерію у відомій частині всесвіту перетворити на папір і чорнило або в комп’ютерний дисковий простір.

У науці, техніці, побуті зустрічаються числа з великою кількістю розрядів. У математиці такі числа часто записують в експоненціальній формі, тобто з використанням мантиси і порядку.

Великі числа в програмуванні

Довга арифметика — в обчислювальній техніці операції над числами, розрядність яких перевищує довжину машинного слова даної обчислювальної машини. По суті арифметика з великими числами являє собою набір алгоритмів виконання базових операцій (додавання, множення, зведення в степінь …) над числами, реалізованими не апаратно, а програмно, використовуючи більш базові апаратні засоби роботи з числами менших порядків. Окремий випадок - арифметика довільної точності (англ. Arbitrary-precision arithmetic) — відноситься до арифметики, в якій довжина чисел обмежена тільки об'ємом доступної пам'яті.

Великі числа в python

У сучасних мовах програмування суттєвих проблем роботи з досить великими або досить малими числами майже не існує. Але слід враховувати, що математичні операції над досить великими або досить малими числами виконуються повільніше, ніж операції над невеликими числами. У мові Python фактично не існує обмежень на довжину цілих (тип int) і дійсних (тип float) чисел.

Наприклад

>>> 123456789123456789+123456789123456789

246913578246913578

>>> 123456789.123456789+123456789.123456789

246913578.24691358

Приклад

Потрібно визначити, скільки дільників має дане натуральне число?

Такий розв'язок задачі буде працювати правильно, але для великих чисел цей алгоритм дуже повільний. Тому потрібно використовувати інші алгоритми.

#У циклі перевіряємо чи ділиться число n на і, яке змінюється від 1 до n та рахуємо їх кількість

n=int(input())
k=0
for i in range(1,n+1):
    if n%i==0:
        k+=1
print(k)

Скрайбінг


1255: Дільники числа 2

Дано натуральне число n (10^6<=n<=10^12). Потрібно визначити, скільки дільників має дане число?

n=int(input())

m=int(n**0.5)+1

k=0

for i in range(1,m):

if n%i==0:

k=k+1

for j in range(i,0,-1):

if n%j==0:

if j!=n//j:

k=k+1

print(k)