מספר ראשוני – הבדלי גרסאות

הדרך הנאיבית לבדיקת ראשוניות של מספר נתון נקראת "'''חלוקה ניסיונית'''" (Trial division): ניסיון לחלק את המספר הנתון בכל המספרים מ־2 ועד [[שורש ריבועי|לשורש הריבועי]] של המספר הנתון. אם המספר לא התחלק באף אחד ממספרים אלו הוא גם לא ייתחלקיתחלק באף מספר גדול יותר ולכן הוא ראשוני. במספרים קטנים (ובסמוך להפעלת שיטת הנפה של ארטוסתנס), עדיף לבצע את החילוק הניסיוני רק במספרים ראשוניים. לשתי השיטות סיבוכיות <math>\ O(\sqrt{n})</math> או קרוב לזה, והן אינן [[יעילות אלגוריתמית|יעילות]] עבור מספרים גדולים (בני עשרות [[ספרה|ספרות]] עשרוניות).