Како проверити да ли је број прост у Питхон-у

by
Tweet
Share
Share
Pin

Овај водич ће вас научити како да напишете Питхон програм да проверите да ли је број прост или не.

Ако сте икада радили на тестовима кодирања, наићи ћете на математичко питање на тесту за примарност или да проверите да ли је број прост. И током наредних неколико минута научићете да дођете до оптималног решења за ово питање.

У овом водичу ћете:

  • прегледати основе простих бројева,
  • напишите Питхон код да проверите да ли је број прост, и
  • оптимизујте га даље да бисте добили О(√н) алгоритам времена извршавања.

За све ово и више, хајде да почнемо.

Шта је прост број?

Почнимо са прегледом основа простих бројева.

У теорији бројева, за природни број н се каже да је главни ако има тачно два чиниоца: 1 и сам број (н). Подсетите се из ваше школске математике: за број и се каже да је чинилац броја н, ако и дели н једнако. ✅

Следећа табела наводи неколико бројева, све њихове факторе и да ли су прости.

нФацторсИс Приме?11Не21, 2Да31, 3Да41, 2, 4Не71, 7Да151, 3, 5, 15Не

Из горње табеле можемо да запишемо следеће:

  • 2 је најмањи прост број.
  • 1 је фактор сваког броја.
  • Сваки број н је сам за себе фактор.

Дакле, 1 и н су тривијални чиниоци за било који број н. А прост број не би требало да има друге факторе осим ова два.

То значи да када пређете са 2 на н – 1, не би требало да будете у могућности да пронађете нетривијалан фактор који дели н без остатка.

О(н) Алгоритам за проверу да ли је број прост у Питхон-у

У овом одељку, хајде да формализујемо горњи приступ у Питхон функцију.

Можете проћи кроз све бројеве од 2 до н – 1 користећи објекат ранге() у Питхон-у.

У Питхон-у, ранге(старт, стоп, степ) враћа објекат опсега. Затим можете итерирати преко објекта опсега да бисте добили секвенцу од почетка па све до заустављања -1 у корацима корака.

  Како поново мапирати дугмад на Цхромецаст-у помоћу Гоогле ТВ даљинског управљача

Пошто нам је потребан скуп целих бројева од 2 до н-1, можемо навести опсег(2, н) и користити га заједно са фор петљом.

Ево шта бисмо желели да урадимо:

  • Ако нађете број који дели н једнако без остатка, одмах можете закључити да број није прост.
  • Ако сте прешли кроз цео опсег бројева од 2 све до н – 1 а да нисте пронашли број који дели н једнако, онда је број прост.

Питхон функција за проверу основног броја

Користећи горе наведено, можемо наставити и дефинисати функцију ис_приме() на следећи начин.

def is_prime(n):
  for i in range(2,n):
    if (n%i) == 0:
      return False
  return True

Хајде да сада рашчланимо горњу дефиницију функције.

  • Горња функција ис_приме() узима позитиван цео број н као аргумент.
  • Ако пронађете фактор у наведеном опсегу од (2, н-1), функција враћа Фалсе—јер број није прост.
  • И враћа Труе ако пређете целу петљу без проналажења фактора.

Затим, позовимо функцију са аргументима и проверимо да ли је излаз тачан.

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

У излазу изнад, видите да су 2 и 11 прости (функција враћа Труе). А 8 и 9 нису прости (функција враћа Фалсе).

Како оптимизовати Питхон функцију ис_приме()

Овде можемо направити малу оптимизацију. Обратите пажњу на листу фактора у табели испод.

НумберФацторс61, 2, 3, 6101, 2, 5, 10181, 2, 3, 6, 9, 18

Па, можемо видети да је једини фактор од н који је већи од н/2 сам н.

Дакле, ово значи да не морате да вртите петљу све до н – 1. Уместо тога, можете покренути петљу само до н/2.

Ако не нађете нетривијалан фактор до н/2, не можете пронаћи ни иза н/2.

Сада хајде да изменимо функцију ис_приме() да проверимо факторе у опсегу (2, н/2)

def is_prime(n):
  for i in range(2,int(n/2)):
    if (n%i) == 0:
      return False
  return True

Хајде да наставимо и проверимо излаз кроз неколико позива функција.

is_prime(9)
# False

is_prime(11)
# True

Иако може изгледати као да смо оптимизовали, овај алгоритам није ефикаснији од претходног у смислу сложености времена извршавања. У ствари, оба имају О(н) сложеност времена извршавања: пропорционалну вредности н или линеарну у н.

  Како креирати и управљати више ХомеКит домова

Можемо ли боље? Да можемо!

▶ Пређите на следећи одељак да бисте утврдили како да побољшате временску сложеност за тестирање простих бројева.

О(√н) алгоритам за проверу основног броја у Питхон-у

Дешава се да се чиниоци броја јављају у паровима.

Ако је а фактор броја н, онда постоји и фактор б такав да је акб = н, или једноставно, аб = н.

Хајде да то проверимо на примеру.

Табела испод показује факторе броја 18 који се јављају у паровима. Можете потврдити исто за још неколико бројева ако желите.

Такође, имајте на уму да је √18 приближно 4,24.

А у факторима који се јављају у паровима (а, б), можете видети да ако је а мање од 4,24, онда је б веће од 4,24—у овом примеру, (2, 18) и (3, 6).

Фактори 18 у паровима

На слици испод приказани су фактори од 18 уцртани на бројевној правој.

Ако је број н савршен квадрат, имаћете а = б = √н као један од фактора.

▶ Погледајте факторе од 36 у табели испод. Како је 36 савршен квадрат, а = б = 6 је један од фактора. За све остале парове фактора (а, б) важи а < 6 и б > 6.

Фактори 36 у паровима

Сумирајући, имамо следеће:

  • Сваки број н се може написати као н = акб
  • Ако је н савршен квадрат, онда је а = б = √н.
  • А ако је а < б, онда, а < √н и б > √н.
  • Иначе, ако је а > б, онда а > √н и б < √н.

Дакле, уместо да петљате кроз све целе бројеве до н/2, можете изабрати да покренете до √н. И ово је много ефикасније од нашег претходног приступа.

Како да измените ис_приме() у О(√н) алгоритам

Хајде да наставимо са оптимизацијом функције за проверу простих бројева у Питхон-у.

import math
def is_prime(n):
  for i in range(2,int(math.sqrt(n))+1):
    if (n%i) == 0:
      return False
  return True

Сада, хајде да рашчланимо горњу дефиницију функције:

  • Да бисмо израчунали квадратни корен броја, хајде да увеземо Питхон-ов уграђени математички модул и користимо функцију матх.скрт().
  • Како н можда није савршен квадрат, мораћемо да га претворимо у цео број. Користите инт(вар) да пребаците вар у инт.
  • Да бисмо били сигурни да заиста проверавамо до √н, додајемо плус један пошто функција ранге() подразумевано искључује крајњу тачку опсега.
  Водич корак по корак за интеграцију фонтова

Ћелија кода испод потврђује да наша функција ис_приме() ради исправно.

is_prime(8)
# False

is_prime(15)
# False

is_prime(23)
# True

У следећем одељку, хајде да направимо неколико једноставних дијаграма да бисмо визуелно разумели О(н) и О(√н).

Поређење О(н) и О(√н) Визуелно

▶ Покрените следећи исечак кода у окружењу Јупитер бележнице по вашем избору.

import numpy as np
import seaborn as sns
import pandas as pd


n = 20

x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)

Горњи исечак показује како можете да нацртате криве за н и √н за опсег вредности.

  • Користимо функцију НумПи аранге() да креирамо низ бројева.
  • А затим прикупљамо вредности н и √н до, али не укључујући 20, у пандас ДатаФраме.
  • Затим цртамо користећи Сеаборн’с линеплот() функција.

Из графикона испод видимо да је √н знатно мање од н.

Хајде да сада повећамо опсег на чак 2000 и поновимо исте кораке као горе.

import numpy as np
import seaborn as sns
import pandas as pd


n = 2000

x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)

Из горњег дијаграма можете закључити да је О(√н) алгоритам знатно бржи када тестирате да ли је велики број прост.

Ево кратког примера: 2377 је прост број—потврдите ово!😀

Док ће О(н) приступ имати редослед од 2000 корака, О(√н) алгоритам може помоћи да се дође до одговора у само 49 корака.✅

Закључак

⏳ И време је за кратак резиме.

  • Да бисте проверили да ли је број прост, наиван приступ је да се прође кроз све бројеве у опсегу (2, н-1). Ако не нађете фактор који дели н, онда је н просто.
  • Пошто је једини фактор од н већи од н/2 сам н, можете изабрати да покренете само до н/2.
  • Оба горња приступа имају временску сложеност од О(н).
  • Пошто се фактори броја јављају у паровима, можете покренути само до √н. Овај алгоритам је много бржи од О(н). А добитак је приметан када се провери да ли је велики број прост или не.

Надам се да разумете како да проверите да ли је број прост у Питхон-у. Као следећи корак, можете погледати наш водич о Питхон програмима о операцијама са стринговима — где ћете научити да проверите да ли су стрингови палиндроми, анаграми и још много тога.

Видимо се у другом туторијалу. До тада, срећно кодирање!👩🏽‍💻