Мат

За анхны тооноос эхлье даа.

- N натурал тооны хамгийн бага анхны тоон хуваагч нь түүнээс язгуур авсан sqrt(n)-ээс хэтрэхгүй. Эндээс харвал тухайн тооны язгуур хүртлэх бүх тоон дунд ядаж нэг тоо N-г хувааж байвал энэ тоон анхны тоо биш.

- Дараагийн түгээмэл хэрэглэгдэх бодлого бол N хүртлэх бүх анхны тоог олох.

Монголоор анхны тоон тор гэж нэрлэдэг. Sieve-н алгоритм нь дараах байдлаар ажилдаг.

N хүртлэх бүх тоог анхны тоо гэж үзье. i тоологчоо 2-оос эхлээд N хүртэл гүйлгэе. Ингэхдээ хэрэв тухайн i тоо анхны тоо байвал түүнд хуваагдах өөрөөс нь бусад бүх тоог ахны тоо биш болгоно. i=N үед үлдсэн тоонууд анхны тоонууд байна. Алгоритм ингээд болоо.

Дасгал асуулт: i-г хэд хүртэл гүйлгэхэд хангалттай вэ? Мөн ажиллах хугацааны үнэлгээг олно уу.

- Өгөгдсөн хоёр тооны, a b, хамгийн их ерөнхий хуваагчийг ол. Үүнийг англиар greatest common divisor (gcd) гэнэ. a, b хоёрыг хоюуланг нь хуваадаг хамгийн том тоог ол л гэсэн үг. Brute-force хийж үзье.

a = b*q+r хэлбэрт тавигдана. r тэгээс ялгаатай байвал b r хоёрын gcd нь манай бодлогын хариу болно. Иймээс дараах рекурсив функцыг бичиж чадна. Нэг жишээ ажиллаж үзье.

gcd(2336, 1314) ?

2336 = 1314*1 + 1022

            1314 = 1022*1 + 292

                        1022 = 292*3 + 146

                                    292 = 146*2 + 0

- a, b хоёр тоо байхад gcd(a, b) = x*a + y*b байх x, y хоёр тоо олдно. x, y-г олно уу.

Бодолт: a = q*b + r, r!=0 үед gcd(a, b) = gcd(b, r) = b*x` + r*y` байх x`, y` хоёр тоо олдно гэсэн үг. Тэгэхээр:

r = a-q*b

gcd(a, b) = b*x` + r*y` = b*x` + (a-q*b)*y` = y`*a + (x`-q*y`)*b

эндээс

x = y`

y = x` - q*y`

гэсэн үг. Үүнийг өөрөө сайн хийж харна уу!!

- Модулар алгебра.

Чанар болон онолын зүйл бичилгүй шууд хамгийн хэрэглээтэй бодлого бодолтыг нь бичье.

Энгий алгебрад a!=0 байх a нь дурын b-н хувьд a*b=1 байхаар цор ганц утгатай тодорхойлогддог. Харин модулар алгебрад ийм байх албагүй. Жишээ авч үзье.

a=2, mod 26 үед хариу байхгүй. Дээрх b тэгшитгэл биелэх b тоог a-н урвуу тоо гэж нэрлэдэг.

Дараах тоон олонлогийг авч үзье.

Zn = {x E {0..n-1}: x болон n -үүд харилцан анхных}

Зөвхөн Zn харьяалагдах тоонууд урвуу тоотой байна. Батлаарай!

Урвуу тоог олох бодлого нь x*a + y*b = 1 тэгшитгэлд a = a, b=N тавиад дээрх код хүчинтэй.



- Хятадын үлдэгдэлтэй хуваах теорем.

Маш энгийнээр бол a, b, m, n gcd(n, m)=1 бол x=a(mod m) x=b(mod n) байх x-г ол.

Бодолт:

n^(-1) - г n-н урвуу тоо

m^(-1) -г m-н урвуу тоо

тэгвэл x=a*n*n^(-1) + b*m*m^(-1) байна.



source



За маш энгийн болоод маш товч бичлээ. Асуух зүйлүүдээ комментоор бичээрэй. Дуртай хариулна. Матын бодох бодлогуудыг маргааш тавина. Амжилт.