Санның қарапайым болу (немесе болмау) қасиеті қарапайымдық деп аталады. Берілген n санының қарапайымдығын тексерудің қарапайым, бірақ баяу әдісі бөлгіштерді асырып алу деп аталады. Бұл санның n саны 2 -ден бастап. дейінгі бүтін санның еселі ме, жоқ па, соны тексеру. Деректерді қайта есептеуден гөрі әлдеқайда тиімді алгоритмдер үлкен сандардың қарапайымдығын тексеру үшін жасалды. Бұларға Миллер-Рабиннің қарапайымдылық тестісі кіреді, ол тез, бірақ қателік мүмкіндігі аз, және AKS қарапайымдылық тесті полиномиалдық уақыт ішінде әрқашан дұрыс жауап береді, бірақ практикалық қолдану үшін тым ұзақ уақыт алады. Әсіресе, Мерсенн сандары сияқты арнайы түрдегі сандар үшін есептеудің жылдам әдістері бар. 2016 жылдың қаңтар айындағы жағдай бойынша ((жаңарту) ең үлкен қарапайым сан 22 338 618 ондық цифрдан тұрады.
Үлкен сандардың қарапайымдығын ыңғайлы түрде тексеру үшін қолданылатын басқа алгоритмнің аты қандай?
AKS қарапайымдылық тесті