انجمن ریاضی ایران فرهنگ و اندیشه ریاضی 1022-6443 22 2 2003 12 22 آیا n اول است؟ الگوریتمی همه فهم با زمان اجرای چندجمله ای 7 24 94 FA روح الله جهانی پور دانشگاه کاشان، گروه ریاضی Journal Article 2011 08 15 در دوره آموزش ابتدایی با غرابل اراتستن آشنا می شویم. متاسفانه استفاده از این روش برای تعیین اول بودن یک عدد طبیعی مستلزم زمان محاسبه ای متناسب با خود عدد است. از طرفی، طول عدد ورودی به غربال اراتستن با تعداد ارقام دودویی آن متناسب است و لذا الگوریتمی در پیش داریم که زمان اجرای نمایی دارد. به این ترتیب آیا اصلا می توان درباره اول بودن اعداد خیلی بزرگ تصمیم گرفت؟ تعبیر یاضی این پرسش در چارچوب نظریه پیچیدگی محاسبات، ارائه الگوریتمی با زمان اجرای چندجمله ای است. در این مقالهT شرحی توصیفی - تاریخی درباره حل این مساله و ارائه الگوریتم مورد بحث است.