شما در این مسئله تا n/2 رو چک می کنید .اگه یه عدد خیلی بزرگ باشه اونوقت کل زمان برنامه برای این کار تلف می شه.اگه شما یه عدد غیر از خودش ویک رو پیدا کنید که n بر اون بخش پذیر باشه شرط نقض می شه. برای این کار بهتره از 2 تا جذر عدد n رو چک کنیم.هم دامنه اعداد کوچکتره وهم جواب سریعتر پیدا میشه.
if n=2 or 3 is prime
for i=2 to sqr n
if n mod i =0 is not prime
else is prime
پاسخ با نقل قول