حل تشریحی سوال شماره 37 دروس مشترک

می‌خواهیم تابعی داشته باشیم که برای عدد طبیعی داده شده n، در صورت اول بودن آن، مقدار 1 و در صورت اول نبودن آن مقدار صفر را برگرداند. در تابع زیر برای این‌ منظور، کمترین مقدار A که الگوریتم همواره درست جواب دهد، کدام است؟

Is-Prime(n){

for i = 2 to A{

if (n mod i ==0)

return 0

}

return 1

}