Негизги математика: бөлүнүү, ЭЧЖБ, жай сандар
Бөлүнүү, ЭЧЖБ жана ЭКЖЭ, жай сандар, Эратосфендин элеги жана көбөйтүүчүлөргө ажыратуу.
Олимпиадачынын сандык базасы — төрт тема.
1. Бөлүнүү жана калдыктар. Эгер a % b == 0 болсо, a саны b га бөлүнөт. Калдыктар цикл менен кайталанат: сандын акыркы цифрасы — бул n % 10, жуптугу — n % 2.
2. ЭЧЖБ жана ЭКЖЭ. Эң чоң жалпы бөлүүчү Евклиддин алгоритми менен O(log n) убакытта эсептелет (аны тил курсунда жазгансыз). Эң кичине жалпы эселик: ЭКЖЭ(a,b) = a / ЭЧЖБ(a,b) * b — ашып кетпеш үчүн так ушул тартипте.
3. Жай сандар. Бир санды текшерүү — бөлүүчүлөрдү тамырга чейин кыдыруу. Ал эми n ге чейинки БАРДЫК жай сандар керек болсо — Эратосфендин элеги: сандарды жазып чыгып, ар бир жай санга эселерин сызып салабыз.
Эратосфендин элеги: n ге чейинки бардык жай сандар. Киргизиңиз: 50
Элек эмнеге тез: ар бир курама сан өзүнүн жай бөлүүчүлөрү менен сызылат, жалпысынан O(n log log n) чыгат — дээрлик сызыктуу. n = 10⁷ үчүн секундадан аз иштейт.
Ичке жагдай: сызуу 2 * i ден эмес, i * i ден башталат — андан кичине эселиктер мурунку кичине жай сандар менен мурдатан сызылган.
4. Жай көбөйтүүчүлөргө ажыратуу: санды тамырга чейинки бардык бөлүүчүлөргө бөлөбүз; эгер бирден чоң бир нерсе калса — бул акыркы жай көбөйтүүчү.
Жай көбөйтүүчүлөргө ажыратуу. Киргизиңиз: 360
Тапшырма: электин жардамы менен миллиондон кичине канча жай сан бар экенин эсептеңиз (жооп: 78498 — өзүңүздү текшериңиз).
Андан кийин тиркелген «Эки сандын ЭЧЖБ», «Жай санды текшерүү» жана «Сандын факториалы» маселелерин чечип, сабакты өттүм деп белгилеңиз.