किसी नंबर की अभाज्यता जांचना गणित की एक महत्वपूर्ण प्रॉब्लम है। इस प्रॉब्लम को सुलझाने का प्रयत्न कई प्राचीन और आधुनिक गणितज्ञों ने किया है।

इस प्रॉब्लम के लिए सबसे आसान अल्गोरिद्म ट्रायल डिवीज़न है। ये अल्गोरिद्म इस प्रकार काम करता है: मान लीजिए हम जांचना चाहते हैं कि n अभाज्यता है या नहीं है। ये अल्गोरिद्म जाँच करता है कि 2 से लेकर \sqrt{n} तक कोई नंबर n का भाजक है या नहीं। अगर इन में से कोई भाजक है, तो अल्गोरिद्म उत्तर देता है कि n भाज्य है। अगर इन में से कोई भी n का भाजक नहीं है, तो अल्गोरिद्म उत्तर देता है कि n अभाज्य है। इस अल्गोरिद्म की कमी इसकी धीमी गति है। एक 60

Documentation[create]