"erathosthense" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

vahe on 2). *Algarvulisuse kontroll: a). ,,Katse-eksimis meetodil" ­ sellisel juhul on mõtekas proovida kuni väärtuseni , kuna järgnevate arvude hulgas tegurit enam tõenäoliselt ei leidu. b). Fermat' väike teoreem- asendadada arvud Fermat' väikesesse teoreemi. c). Miller-Rabini test- ehkki tegu on tõenäosusliku polünomiaalse meetodiga, on tulemus suhteliselt usaldusväärne, kuna eksimisvõimalus on harilikult 0,01% või vähemgi. *Erathosthense sõel- (Antiikne) meetod selekteerimaks n naturaalarvu seast välja algarve. Üles kirjutatakse kõik antud vahemiku naturaalarvud 1,2,3....n ning nende seast hakatakse järjest välja kriipsutama n-1 kordseid arve. Alles jäävad vaid algarvud. [24].Naturaalarvude kanooniline kuju. Suurim ühistegur ja vähim ühiskordne. Iga naturaalarvu n saab esitada kujul n = , ehk sisuliselt teatud (astmesse tõstetud) algarvude korrutisena. Arv n jagub kõigi nende algarvudega p