چگونه تشخیص دهیم یک عدد اول است

برنامه‌ای بنویسید که یک عدد صحیح از کاربر بگیرد و در پاسخ اعلام کند که عدد مذکور یک عدد اول است یا خیر؟

چگونه تشخیص دهیم یک عدد اول است

برای حل یک مسئله، اول باید بفهمیم که سوال مورد نظر چه چیزی از ما خواسته است. در اینجا ابتدا باید یک عدد صحیح از کاربر بگیریم که با وارد کردن دستور ورودی، آن را انجام می‌دهیم.

برای اطلاعات بیشتر در این مورد، مقاله‌ی ورودی و خروجی در پایتون را مطالعه نمایید.

در قسمت بعدی، از ما خواسته شده که اول بودن، عدد ورودی را بررسی کنیم. که ما نخست باید بدانیم، عدد اول چیست؟ و سپس برای تشخیص آن، از چه الگوریتمی استفاده کنیم؟

الگوریتم، مجموعه دستورالعمل‌های پشت‌ سر هم و مرتبی است که به رایانه می‌دهیم تا با اجرای به ترتیب آنها، مسائل را حل کند. هر مسئله می‌تواند از طریق چندین الگوریتم، حل شود اما الگوریتمی کاراتر است که بهینه‌ شده و از سرعت بالاتری برخوردار باشد.

همان‌طور که می‌دانید به صورت خلاصه، عددی را عدد اول گویند که به جز عدد یک و خودش، به هیچ عدد دیگری بخش‌پذیر نباشد.

اگر هر عدد را بر اعداد کوچک‌تر از خودش تقسیم کنیم و فقط به یک بخش‌پذیر باشد، عدد اول است. برای این امر، از الگوریتم‌های مختلفی می‌توان استفاده کرد که در این مقاله، از سه الگوریتم متفاوت برای پیاده سازی برنامه‌ی تشخیص عدد اول در پایتون استفاده می‌کنیم. تا شما کاربرد الگوریتم در برنامه‌نویسی را بهتر درک کنید.

الگوریتم اول برنامه‌ی تشخیص عدد اول در پایتون به این صورت است:

ابتدا یک عدد را از کاربر می‌گیریم. برای گرفتن ورودی از کاربر، از دستور input() و برای تبدیل رشته به عدد صحیح از دستور int() استفاده می‌کنیم. عدد ورودی را در متغیر number قرار می‌دهیم. به این صورت:

اکنون متغیر accumulator که جمع‌کننده‌ی تعداد مقسوم‌علیه‌ها است، را تعریف می‌کنیم و عدد 0 را به آن اختصاص می‌دهیم. به این صورت:

برای تقسیم عدد ورودی بر اعداد کوچک‌تر مساوی خودش، از یک حلقه‌ی تکرار for استفاده می‌کنیم. از آنجا که قصد داریم خود متغیر number نیز در حلقه باشد، یک را به آن اضافه می‌کنیم.

در حلقه، اگر باقیمانده‌ی تقسیم ورودی بر عدد جاری حلقه، برابر صفر بود یکی به متغیر accumulator اضافه می‌کنیم. به این صورت:

وقتی حلقه‌ی ما به پایان می‌رسد، باید مقدار متغیر accumulator را بررسی کنیم. اگر مساوی 2 بود، پیغام “عدد اول است” و در غیر این‌صورت پیغام ” عدد اول نیست” را چاپ می‌کنیم. برای این کار از دستور if-else استفاده می‌کنیم. به این صورت:

ما به راحتی توانستیم با این الگوریتم ساده، برنامه‌ی پایتون تشخیص عدد اول را بنویسیم. کد این برنامه را می‌توانید در زیر ببینید.

در الگوریتم اول با استفاده از یک جمع‌کننده‌ی تعداد مقسوم‌علیه‌ها توانستیم برنامه‌ای بنویسیم که عدد اول را تشخیص دهد. اکنون می‌خواهیم از الگوریتمی استفاده کنیم که برای پیاده سازی برنامه‌ی تشخیص عدد اول در پایتون، نیاز به جمع‌کننده‌ی تعداد مقسوم‌علیه‌ها ندارد.

مانند کد قبلی، ابتدا از کاربر یک عدد صحیح می‌گیریم و در متغیر number ذخیره می‌کنیم. به این صورت:

با استفاده از دستور شرطی if-else، اگر عدد ورودی بزرگ‌تر از یک باشد، برای بررسی به بلوک if هدایت می‌شود. و اگر عدد یک باشد در بلوک else پیغام “عدد شما، عدد اول نیست” چاپ می‌شود. به این صورت:

اکنون به سراغ نوشتن کدهای بلوک if می‌رویم. طبق الگوریتم ما باید عدد ورودی را بر اعداد 2 تا نصف خودش، برای بخش‌پذیر بودن بررسی کنیم. پس یک حلقه‌ی تکرار for با دامنه‌ی اعداد از 2 تا عدد ورودی تقسیم بر 2 می‌نویسیم. به این صورت:

نکته: از آنجا که الگوریتم خوب، باید بهینه شده باشد، ما عدد ورودی را تا نصف خودش بررسی می‌کنیم. زیرا هر عدد اگر تا نصف خودش بر عددی بخش‌پذیر نباشد، بر اعداد بزرگتر از نصفش نیز، بخش‌پذیر نیست.

در حلقه، اگر باقیمانده‌ی تقسیم عدد ورودی بر i مساوی صفر بود، پیغام ” عدد اول نیست” را چاپ می‌کنیم. سپس با استفاده از دستور break برنامه را به پایان می‌رسانیم. به این صورت:

نکته: چون عدد یک و number در حلقه نیستند، اگر number بر هر عددی بخش‌پذیر باشد، آن عدد، اول نیست.

اما اگر حلقه‌ی for بدون هیچ اتفاقی به پایان برسد، در یک else پیغام “عدد اول است” را چاپ می‌کند. به این صورت:

به این طریق ما به کمک الگوریتمی دیگر توانستیم برنامه‌ی پایتون تشخیص عدد اول را بنویسیم. کد این برنامه به این صورت است:

نکته‌ی حائز اهمیت، این است که الگوریتم دوم به دلیل بررسی number/2، بهینه‌تر و از سرعت بالاتری برخوردار است. پس برای نوشتن برنامه‌هایتان، الگوریتمی استفاده کنید که بهینه‌‌شده باشد، زیرا سرعت اجرای برنامه‌ بیشتر و حافظه کمتری اشغال می‌کند. در الگوریتم بعدی، کد ما بهینه‌تر خواهد شد.

در الگوریتم سوم برنامه‌ی تشخیص عدد اول در پایتون قصد داریم از الگوریتمی استفاده کنیم که خیلی بهینه‌شده‌تر و سریع‌تر است. در این الگوریتم به جای آن که تا عدد ورودی بررسی شود، تا جذر عدد ورودی بررسی خواهد شد.

طبق موارد قبلی، ابتدا یک ورودی از کاربر می‌گیریم. به این صورت:

براساس الگوریتم، برای آن که برنامه در هر گام به پایان برسد، آن را در حلقه‌ای نوشته که یک‌دور می‌زند. پس ما از یک حلقه‌ی while استفاده می‌کنیم و یک متغیر boolean به نام active با مقدار True تعریف می‌کنیم. به این صورت:

در داخل حلقه، با شرط اول، اگر number کوچک‌تر مساوی یک باشد، پیغام “عدد اول نیست” چاپ می‌شود. سپس با دستور break از برنامه خارج می‌شود. به این صورت:

با عدم برقراری شرط اول، با شرط دوم، اگر number کوچک‌تر مساوی 3 باشد، پیغام “عدد اول است” چاپ می‌شود. سپس با دستور break از برنامه خارج می‌شود. به این صورت:

با برقرار نبودن شرط دوم، به سراغ نوشتن شرط سوم می‌رویم. اگر باقیمانده‌ی تقسیم‌های number بر 2 یا number بر 3، مساوی 0 باشد، پیغام “عدد اول نیست” چاپ می‌شود. سپس با دستور break از برنامه خارج می‌شود. به این صورت:

اکنون به گام 5 الگوریتم می‌رسیم، یک متغیر به نام i تعریف کرده و 5 را به آن اختصاص می‌دهیم. سپس یک حلقه‌ی while می‌نویسیم که تا شرط i*i کوچک‌تر مساوی number باشد، ادامه پیدا می‌کند. به این صورت:

در حلقه، اگر باقیمانده‌ی تقسیم‌های number بر i یا number بر i+2، مساوی 0 باشد، پیغام “عدد اول نیست” را چاپ می‌کند. سپس با دستور break از برنامه خارج می‌شود، در غیر این صورت مقدار 6 را به i اضافه می‌کند. به این صورت:

 اکنون برای آن که حلقه‌ی while اولی به پایان برسد، مقدار متغیر active را به False تغییر می‌دهیم. سپس پیغام “عدد شما، یک عدد اول است” را چاپ می‌کنیم. به این صورت:

به این ترتیب،  ما با یک الگوریتم سریع و بهینه، موفق به نوشتن یک برنامه پایتون تشخیص عدد اول شدیم. کد کامل این الگوریتم را در زیر ببینید.

برای نوشتن یک تابع برای تشخیص اول بودن اعداد، می‌توانیم از هر سه الگوریتم بالا استفاده کنیم. اما ما ترجیح می‌دهیم از الگوریتم سوم استفاده کنیم زیرا بهینه‌تر است.

توضیحات کافی در خصوص هر سه الگوریتم‌ در برنامه‌نویسی دادیم. فقط لازم است بدانید، خروجی تابع ما یک boolean است. اگر عدد ورودی، اول باشد، خروجی True و اگر عدد اول نباشد، خروجی False خواهد بود. کد تابع ما به این صورت خواهد بود:

چگونه تشخیص دهیم یک عدد اول است

جمع‌بندی:

با نوشتن یک برنامه‌ی کاربردی پایتون، با سه الگوریتم و روش مختلف به شما نشان دادیم که یک برنامه‌ نویس، چگونه باید تفکر الگوریتمی داشته باشد و چگونه یک الگوریتم را به کد تبدیل کند. تمامی الگوریتم‌ها در مقادیر کوچک، مشکل سرعت نخواهند داشت و این محاسبه اعداد بزرگ است که نشان می‌دهد آیا یک الگوریتم و برنامه‌ی پایتون بهینه‌شده است یا خیر؟ لذا شما در حین اینکه برنامه‌نویسی می‌آموزید، به سراغ یادگیری الگوریتم‌ها نیز بروید تا توانایی بهینه‌سازی برنامه‌هایتان را داشته باشید.

در قسمت بعدی این مجموعه مقالات نوشتن برنامه‌ی مقلوب یک عدد در پایتون، را به شما آموزش خواهیم داد. با ما همراه باشید.

اگر به یادگیری بیشتر در زمینه‌ی برنامه نویسی پایتون علاقه داری، یادگیری زبان پایتون بسیار ساده است. و با شرکت در دوره‌ی متخصص پایتون توسعه وب در آینده می‌تونی اپلیکیشن موبایل و دسکتاپ بسازی و وارد حوزه‌ی هوش مصنوعی هم شوی.

چه امتیازی به این مقاله می دید؟

1
2
3
4
5

.stars {
background: url(‘data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAB4AAABaCAYAAACv+ebYAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAABx0RVh0U29mdHdhcmUAQWRvYmUgRmlyZXdvcmtzIENTNXG14zYAAAAWdEVYdENyZWF0aW9uIFRpbWUAMDcvMDMvMTNJ3Rb7AAACnklEQVRoge2XwW3bMBSGPxa9NxtIGzTAW8DdRL7o3A0qb+BrdNIm9QAm0G7gbJBMwB5MoVJNUSRFIXGqHwhkmXr68hOPNH9ljOEt9OlNqBs4RlrrSmtdpdZ/Ti0EGnvtUoqTHFunBVCkuk6d6mbi83rggdteSa5THDeB3+UDO9z2inatXFum1roESuAReAB29vp15n2/gRfgZK+/gIuIXLxgrfUO+Bnzn0fom4ic+pvRVNuB/QrQ/RB6A7bwLjN8b985krO5MsKd0ElwJvgk1AteCPdCYWI5/SutddQxRUTU3DOzG4hd01EKqQnZuaLBITUh4F0CeLYm5CDw6PjuFTjaz9+BLwE1I8VO9StwAEoRaUSkseMHO+aqcWq2qwcdfQCOIvIy8dwDV/c/YL6zvWDbnQ3QuH5hltQEreM1dH/n6g28gT8eWLVUqqVKrb+vtGidFkCR6vp+0uLAba8k1/eRFh1ue0W7dv4sqpaSjGnR1Fy8YNWyY8W0aGpO/c1oqu3AKmlxCL0BW3iXGb637xzJ2VwZ4U7oJDgTfBLqBS+Ee6EQeMpULVFHUVOzPC3aNR2lkJotLbr0vtKiqWlMTcNaaXHQ0QfgaGqcaVG1jNLibGcbYyb/eDIlT6bjyZS+51JqtrS4gTfw/wzWqkKrKrU8fQPR6gKAmDKlPM3x1WkBFKmu0xxf3fZR5jnFdbzjv257JbmOdzx22yvadZzjW7e9ol27HWtVkjEtIubiB2u1Y8W0iJhTfzOe6uvAKmlxCL0FX+FdZvjevnMkd3Plgzuh0+A88EmoH7wM7oVC6AaiVdwuI2Z5WrRrOk4BNVtadOl9pUXENIhpWCstDjr6ABwR40yLaDVKi7Od7U1/Z0pzpjNngtNiaM2WFj8++A+motm0NTqjmwAAAABJRU5ErkJggg==’) repeat-x 0 0;
width: 150px;
margin: 0 auto;
direction: ltr;
}
.ie7 form .stars {
*zoom: 1;
}
.stars:before,
.stars:after {
display: table;
content: “”;
}
.stars:after {
clear: both;
}
.stars input[type=”radio”] {
position: absolute;
opacity: 0;
filter: alpha(opacity=0);
}
.stars input[type=”radio”].star-5:checked ~ span {
width: 100%;
}
.stars input[type=”radio”].star-4:checked ~ span {
width: 80%;
}
.stars input[type=”radio”].star-3:checked ~ span {
width: 60%;
}
.stars input[type=”radio”].star-2:checked ~ span {
width: 40%;
}
.stars input[type=”radio”].star-1:checked ~ span {
width: 20%;
}
.stars label {
display: block;
width: 30px;
height: 30px;
margin: 0!important;
padding: 0!important;
text-indent: 999em;
float: left;
position: relative;
z-index: 10;
background: transparent!important;
cursor: pointer;
}
.stars label:hover ~ span {
background-position: 0 -30px;
}
.stars label.star-5:hover ~ span {
width: 100% !important;
}
.stars label.star-4:hover ~ span {
width: 80% !important;
}
.stars label.star-3:hover ~ span {
width: 60% !important;
}
.stars label.star-2:hover ~ span {
width: 40% !important;
}
.stars label.star-1:hover ~ span {
width: 20% !important;
}
.stars span {
display: block;
width: 0;
position: relative;
top: 0;
left: 0;
height: 30px;
background: url(‘data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAB4AAABaCAYAAACv+ebYAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAABx0RVh0U29mdHdhcmUAQWRvYmUgRmlyZXdvcmtzIENTNXG14zYAAAAWdEVYdENyZWF0aW9uIFRpbWUAMDcvMDMvMTNJ3Rb7AAACnklEQVRoge2XwW3bMBSGPxa9NxtIGzTAW8DdRL7o3A0qb+BrdNIm9QAm0G7gbJBMwB5MoVJNUSRFIXGqHwhkmXr68hOPNH9ljOEt9OlNqBs4RlrrSmtdpdZ/Ti0EGnvtUoqTHFunBVCkuk6d6mbi83rggdteSa5THDeB3+UDO9z2inatXFum1roESuAReAB29vp15n2/gRfgZK+/gIuIXLxgrfUO+Bnzn0fom4ic+pvRVNuB/QrQ/RB6A7bwLjN8b985krO5MsKd0ElwJvgk1AteCPdCYWI5/SutddQxRUTU3DOzG4hd01EKqQnZuaLBITUh4F0CeLYm5CDw6PjuFTjaz9+BLwE1I8VO9StwAEoRaUSkseMHO+aqcWq2qwcdfQCOIvIy8dwDV/c/YL6zvWDbnQ3QuH5hltQEreM1dH/n6g28gT8eWLVUqqVKrb+vtGidFkCR6vp+0uLAba8k1/eRFh1ue0W7dv4sqpaSjGnR1Fy8YNWyY8W0aGpO/c1oqu3AKmlxCL0BW3iXGb637xzJ2VwZ4U7oJDgTfBLqBS+Ee6EQeMpULVFHUVOzPC3aNR2lkJotLbr0vtKiqWlMTcNaaXHQ0QfgaGqcaVG1jNLibGcbYyb/eDIlT6bjyZS+51JqtrS4gTfw/wzWqkKrKrU8fQPR6gKAmDKlPM3x1WkBFKmu0xxf3fZR5jnFdbzjv257JbmOdzx22yvadZzjW7e9ol27HWtVkjEtIubiB2u1Y8W0iJhTfzOe6uvAKmlxCL0FX+FdZvjevnMkd3Plgzuh0+A88EmoH7wM7oVC6AaiVdwuI2Z5WrRrOk4BNVtadOl9pUXENIhpWCstDjr6ABwR40yLaDVKi7Od7U1/Z0pzpjNngtNiaM2WFj8++A+motm0NTqjmwAAAABJRU5ErkJggg==’) repeat-x 0 -60px;
-webkit-transition: -webkit-width 0.5s;
-moz-transition: -moz-width 0.5s;
-ms-transition: -ms-width 0.5s;
-o-transition: -o-width 0.5s;
transition: width 0.5s;
}

با سلام
ببخشید راستش من این الگوریتم سوم رو مخصوصا اونجا که i = i + 6 کرده رو متوجه نشدم ، امکانش هست بیشتر توضیح بدید؟

سلام دوست عزیز،
در این الگوریتم به جای اینکه عدد مورد نظر را بر تمامی اعداد قبل خودش تقسیم کنیم، ابتدا آن را بر 2 و 3 تقسیم می کنیم اگر بخش پذیر بود خیلی راحت متوجه می‌شویم که عدد اول نیست و اگر بخش‌پذیر نبود آن بر اعداد 5 و 7 تقسیم می کنیم و باز اگر بخش پذیر بود عدد ما اول نیست و در غیر این صورت i خود را که 5 باشد با 6 جمع می کنیم (i = i+6) و دوباره مرحله قبل را که بر 5 و 7 بود را این مرتبه با 11 و 13 امتحان می کنیم.. و این کار را ادامه می دهیم تا وقتی که i*i بزرگتر مساوی عدد مورد نظرمان شود. اگر هیچکدام از این شرایط برقرار نشد پیغام عدد ما اول است را چاپ می کنیم. امیدوارم الان بهتر متوجه شده باشید.

الگوریتم دوم باگ داره
4 رو بدی بهش prime میده

سلام , اقا زحمت کشیدید , ولی بهتر نبود کد هاتون رو اول تست میکردید بعد مینوشتید . چون خیلی اشتباه نوشته شده , مثلا در الگوریتم دوم که در اخر که کد ها رو کامل نوشتید ایندنت else زیر for نوشته شده , باید زیر if باشد . اشکال دیگر اینکه جلوی کلمه break پرانتز گذاشتید!!

سلام دوست عزیز، تمامی کدها تست شده است.. درمورد else در for این از ویژگی‌های زبان پایتون است اگر قصد آشنایی بیشتر در این مورد را دارید از این لینک استفاده کنید:
https://book.pythontips.com/en/latest/for_-_else.html
درمورد پرانتز در break نیز در یک مورد، اشتباه تایپی رخ داده. ممنون از اینکه اطلاع دادید.

هدف مجموعه سون لرن افزایش سطح کیفیت آموزش و ساختن راهی برای ورود دانشجویان به بازار کار تخصصی است

بدلیل شرایط حساس کنونی و شیوع کرونا تیم سون لرن تا اطلاع ثانوی به صورت دورکار فعالیت دارد.

تلفن : ۰۲۱-۲۸۴۲۷۷۵۰      
پشتیبانی تلگرام : @sup_7Learn

یک عدد اول (به انگلیسی: Prime Number)، عددی طبیعی بزرگتر از ۱ است که نتوان آن را به صورت ضرب دو عدد طبیعی کوچکتر نوشت. (یعنی یکی از آن‌ها نمی‌تواند با خود عدد برابر باشد). عدد طبیعی بزرگتر از ۱ که اول نباشد را عدد مرکب گویند. به عنوان مثال ۵ یک عدد اول است، چون تنها روشی که می‌توان آن را به صورت ضرب دو عدد طبیعی نوشت به صورت 1×5{displaystyle 1times 5} یا 5×1{displaystyle 5times 1} است که شامل خود ۵ می‌شود (دو عددی که در ضرب می‌آیند باید از خود ۵ کوچکتر باشند). اما به عنوان مثال ۶ یک عدد مرکب است، چرا که می‌توان آن را به صورت 2×3{displaystyle 2times 3} نوشت که هردوی آن‌ها از ۶ کوچک‌ترند. اعداد اول در نظریه اعداد به دلیل قضیه اساسی حساب نقش محوری دارند، این قضیه می‌گوید: هر عدد طبیعی بزرگتر از ۱ یا اول است یا می‌توان آن را به ضرب اعداد اول تجزیه کرد، که این تجزیه در حد ترتیب یگانه است.

خاصیت اعداد اول را اول بودن می‌گویند. یک روش کند برای چک کردن اول بودن یک عدد مثل n{displaystyle mathrm {n} }، آزمون تقسیم است. این آزمون بخش پذیر بودن n{displaystyle mathrm {n} } بر هر عدد صحیح بین ۲ و n{displaystyle {sqrt {n}}} را چک می‌کند. الگوریتم‌های سریع تری نیز وجود دارند، مثل آزمون اول بودن میلر-رابین که سریع است اما احتمال رخ دادن درصدی خطا نیز در آن وجود دارد. آزمون دیگر، آزمون اول بودن AKS است، که همیشه جواب صحیح بدست می‌دهد، اما مرتبه زمانی آن چندجمله‌ای است و برای کاربردهای عملی بسیار کند می‌باشد. روش‌های بسیار سریعی برای آزمون اول بودن اعداد خاصی مثل اعداد مرسن نیز وجود دارد. تا دسامبر ۲۰۱۸ بزرگترین عدد اول شناخته شده در سیستم ده-دهی ۲۴٬۸۶۲٬۰۴۸ رقم دارد.[۱]

اقلیدس حدود ۳۰۰ قبل از میلاد اثبات کرد که بی‌نهایت عدد اول وجود دارد. با این حال، توزیع اعداد اول در میان اعداد طبیعی را می‌توان از نظر آماری مدلسازی کرد. اولین نتیجه ای که در این جهت حاصل شد قضیه اعداد اول بود که در انتهای قرن نوزدهم بدست آمد. این قضیه می‌گوید که احتمال اول بودن یک عدد طبیعی تصادفی با تعداد ارقام آن (یعنی لگاریتم آن عدد) رابطه عکس دارد.

چندین سؤال تاریخی در ارتباط با اعداد اول هنوز لاینحل مانده‌اند. این سوالات شامل حدس گلدباخ می‌شود، این حدس می‌گوید که هر عدد صحیح زوج بزرگتر از ۲ را می‌توان به صورت جمع دو عدد اول بیان کرد. یکی دیگر از این سؤالات حدس اعداد اول دوقلو است، که می‌گوید تعداد اعداد اولی که تفاضلشان فقط ۲ باشد بی‌نهایت است. چنین سؤالاتی موجب پیشرفت شاخه‌های مختلف نظریه اعداد گشتند که در این مسیر بر روی جنبه‌های تحلیلی و جبری اعداد تمرکز شده‌است. اعداد اول در چندین مسیر فناوری اطلاعات استفاده شده‌اند مثل رمزنگاری کلید عمومی که به سخت بودن تجزیه اعداد بزرگ به عوامل اولشان تکیه می‌کند. در جبر مجرد، اشیائی وجود دارند که به صورت تعمیم یافته شبیه اعداد اول عمل می‌کنند، مثل عناصر اول و ایده‌آل‌های اول.

عدد اول عددی طبیعی بزرگ‌تر از ۱ است که بر هیچ عددی به جز خودش و ۱ بخش‌پذیر نباشد.[۲] تنها استثنا عدد ۱ است که جزو این اعداد قرار نمی‌گیرد. اگر عددی طبیعی و بزرگتر از ۱ اول نباشد مرکب است.[۳]

چگونه تشخیص دهیم یک عدد اول است

پیدا کردن رابطه‌ای جبری برای اعداد اول جزء یکی از معماهای ریاضی باقی مانده‌است و هنوز کسی به فرمولی برای آنها دست نیافته‌است.

دنبالهٔ اعداد اول به این صورت شروع می‌شود:

۲، ۳، ۵، ۷، ۱۱، ۱۳، ۱۷، ۱۹، ۲۳، ۲۹، ۳۱، ۳۷، ۴۱، ۴۳، ۴۷، ۵۳، ۵۹، ۶۱، ۶۷، ۷۱، ۷۳، ۷۹، ۸۳، ۸۹، ۹۷، ۱۰۱، ۱۰۳، ۱۰۷، ۱۰۹، ۱۱۳، ۱۲۷، ۱۳۱، ۱۳۷، ۱۳۹، …[۴]

به این اثبات دقت کنید از برهان خلف استفاده می‌کنیم:

فرض خلف : اعداد اول متناهی است.

اعداد اول را در هم ضرب می‌کنیم.

P1,P2,P3,…,Pn{displaystyle P_{1},P_{2},P_{3},…,P_{n}}

ضرب اعداد از Pi{displaystyle P_{i}} بزرگ‌تراست.

P1×P2×P3×…×Pn>Pi{displaystyle P_{1}times P_{2}times P_{3}times …times P_{n}>P_{i}}

P1×P2×P3×…×Pn+1>Pi{displaystyle P_{1}times P_{2}times P_{3}times …times P_{n}+1>P_{i}}

P1×P2×P3×…×Pn+1=Pi1…Pik{displaystyle P_{1}times P_{2}times P_{3}times …times P_{n}+1=P_{i_{1}}…P_{i_{k}}}

P1×P2×P3×…×Pn+1=Pi×X{displaystyle P_{1}times P_{2}times P_{3}times …times P_{n}+1=P_{i}times X}

Pi1×…×Pik=Pi×X{displaystyle P_{i_{1}}times …times P_{i_{k}}=P_{i}times X}

P1×P2×P3×…×Pn+1=Y+1{displaystyle P_{1}times P_{2}times P_{3}times …times P_{n}+1=Y+1}

Pi1×Y+1=Pi1×X{displaystyle P_{i_{1}}times Y+1=P_{i_{1}}times X}

Pi1×X−Pi1×Y=1{displaystyle P_{i_{1}}times X-P_{i_{1}}times Y=1}

Pi1×(X−Y)=1{displaystyle P_{i_{1}}times (X-Y)=1}

Pi1=1{displaystyle P_{i_{1}}=1}

که عدد یک جزء اعداد اول نیست پس به تناقض می‌رسیم و فرض خلف باطل است. اعداد اول نامتناهی هستند.

k عدد اول وجود دارد.

حدس گلدباخ (تاکنون اثبات نشده): هر عدد زوج را می‌توان به شکل جمع دو عدد اول نوشت.

2k=pn+pm{displaystyle 2k=p_{n}+p_{m}}

مثال به شرح ذیل می‌باشد:

4=2+2{displaystyle 4=2+2}

6=3+3{displaystyle 6=3+3}

8=5+3{displaystyle 8=5+3}

10=5+5{displaystyle 10=5+5}

12=7+5{displaystyle 12=7+5}

14=7+7{displaystyle 14=7+7}

16=11+5{displaystyle 16=11+5}

18=11+7{displaystyle 18=11+7}

20=13+7{displaystyle 20=13+7}

22=11+11{displaystyle 22=11+11}

24=13+11{displaystyle 24=13+11}

26=19+7{displaystyle 26=19+7}

چگونه تشخیص دهیم یک عدد اول است

۲. حدس قوی گلدباخ: هر عدد فرد بزرگتر از ۵ را می‌توان به صورت مجموع ۳ عدد اول نوشت.

در ریاضیات تابع شمارش اعداد اول تابعی است که برای بیان تعداد اعداد اول به کار می‌رود و آن را با نماد π(x){displaystyle pi (x)} نمایش می‌دهند.

ریاضیدان فرانسوی پیر دوسارارت ثابت کرد که برای x ≥ ۵۹۹ رابطه زیر برقرار است:

xln⁡x(1+1ln⁡x)<π(x)<xln⁡x(1+1ln⁡x+2.51(ln⁡x)2).{displaystyle {frac {x}{ln x}}left(1+{frac {1}{ln x}}right)<pi (x)<{frac {x}{ln x}}left(1+{frac {1}{ln x}}+{frac {2.51}{(ln x)^{2}}}right).}

همچنین ثابت کرد که برای هر x ≥ ۳۵۵۹۹۱:

xln⁡x+2<π(x)<xln⁡x−4{displaystyle {frac {x}{ln x+2}}<pi (x)<{frac {x}{ln x-4}}}

بعدها ثابت شد که برای هر ε>۰ وجود دارد عددی طبیعی ماننده s که برای هر x>s رابطه زیر برقرار است:

xln⁡x−(1−ε)<π(x)<xln⁡x−(1+ε).{displaystyle {frac {x}{ln x-(1-varepsilon )}}<pi (x)<{frac {x}{ln x-(1+varepsilon )}}.}

اگرπ(x){displaystyle pi (x)} تعداد اعداد اول کمتر از x{displaystyle x} باشد

آنگاه
limx→∞π(x)x/ln(x)=1{displaystyle lim _{xto infty }{frac {pi (x)}{x/ln(x)}}=1}

با استفاده از قضیه اعداد اول می‌توان اثبات کرد که:

limx→∞p(x)xln⁡(x)=1{displaystyle lim _{xto infty }{frac {p(x)}{xln(x)}}=1}

که در آن تابع p(x){displaystyle p(x)}، تابع مولد اعداد اول باشد. یعنی x امین عدد اول p(x)={displaystyle p(x)=}

اثبات مطلب بالا به شرح زیر است:

می‌دانیم
limx→∞π(x)x/ln(x)=1{displaystyle lim _{xto infty }{frac {pi (x)}{x/ln(x)}}=1}

π(x)∼xln⁡x.{displaystyle pi (x)sim {frac {x}{ln x}}.!}

می‌دانیم توابع p(x){displaystyle p(x)} و π(x){displaystyle pi (x)} معکوس هم هستند. یعنی:

p−1(x)=π(x){displaystyle p^{-1}left(,x,right)=pi (x)}

در نتیجه می‌توان با حل معادله π(x)=x{displaystyle pi (x)=x} تابع p(x){displaystyle p(x)} را یافت.

می‌دانیم π(x)∼xln⁡x.{displaystyle pi (x)sim {frac {x}{ln x}}.!}

پس با حل معادله xln⁡x=x{displaystyle {frac {x}{ln x}}=x} می‌توان هم‌ارزی برای p(x){displaystyle p(x)} یافت.

به روش تکرار ساده معادله را حل می‌کنیم.

x1ln⁡x=x2{displaystyle {frac {x_{1}}{ln x}}=x_{2}}

x1=x2ln⁡(x){displaystyle {x_{1}}=x_{2}ln(x)}

p(x)=xln⁡(x){displaystyle p(x)=xln(x)}

اما باید توجه داشت چون به جای π(x){displaystyle pi (x)} از تابع هم ارز آن استفاده شده پس:

p(x)∼ xln⁡(x){displaystyle p(x)sim xln(x)}

در نتیجه:

limx→∞p(x)xln⁡(x)=1{displaystyle lim _{xto infty }{frac {p(x)}{xln(x)}}=1}

قضیه ویلسون راهی برای تشخیص اعداد اول است.
این قضیه بیان می‌کند به ازای هر عدد اول مانند p{displaystyle ;p} داریم (p−1)!≡−1(modp){displaystyle ;(p-1)!equiv -1{pmod {p}}}

این قضیه دوشرطی است بنابراین راهی برای تشخیص اعداد اول از مرکب است یعنی:

برای هر عدد صحیح x اگر رابطه زیر برقرار باشد آنگاه x عددی اول است در غیر این صورت x عددی مرکب است.

{displaystyle ;} (x−1)!≡−1(modx){displaystyle ;(x-1)!equiv -1{pmod {x}}}

این قضیه تعمیم‌هایی به شکل زیر دارد:

تعمیم گاوس: کارل فریدریش گاوس ریاضیدان آلمانی در سال ۱۸۰۰ میلادی ثابت کرده که برای هر عدد طبیعی m>۲ عدد اول p

∏k=1gcd(k,m)=1mk ≡{−1(modm)if m=4,pα,2pα1(modm)otherwise{displaystyle prod _{k=1 atop gcd(k,m)=1}^{m}!!k equiv {begin{cases}-1{pmod {m}}&{text{if }}m=4,;p^{alpha },;2p^{alpha }\;;,1{pmod {m}}&{text{otherwise}}end{cases}}}

در اینجا α{displaystyle alpha } عددی صحیح و مثبت است.

بزرگ‌ترین عدد اول کشف شده تا (۲۰۱۶) برابر دو به توان ۷۴ میلیون و ۲۰۷ هزار و ۲۸۱ منهای یک است.[۶] این عدد ۲۲٬۳۳۸٬۶۱۸ رقم دارد و یک عدد مرسن است. عدد مرسن عددی است که برابر ۲ به توان n منهای یک است.
در سال ۲۰۱۸، طولانی‌ترین عدد اول که دارای ۲۳ میلیون رقم است؛ کشف شد. این عدد اول نیز یک عدد مرسن است که در جریان محاسبات در رایانه یک مهندس برق به نام جاناتان پیس در آمریکا در جریان پروژه‌ای برای کشف اعداد اول به نام «تحقیق اینترنتی بزرگ عدد مرسن» (GIMPS) کشف شد. این عدد را به اختصار و به‌طور قراردادی، M77232917 نامیده‌اند. پژوهش‌ها برای یافتن عددهای اول بزرگ دشوار و نیازمند نرم‌افزارهای خاص و همکاری علمی پژوهشگران هستند.[۷]

مؤسسه Electronic Frontier Foundation جایزه‌ای به مبلغ صدهزار دلار برای اولین کسی که یک عدد اول با حداقل ۱۰ میلیون رقم پیدا کند در نظر گرفته‌است. همچنین مبلغ ۱۵۰ هزار دلار برای کسی که یک عدد اول با ۱۰۰ میلیون رقم و ۲۵۰ هزار دلار برای ۱ میلیارد رقم در نظر گرفته شده‌است. این مؤسسه ممکن است مبلغ ۱۰۰ هزار دلار برای دپارتمان ریاضی دانشگاه UCLA که موفق به کشف یک عدد اول ۱۳ میلیون رقمی شدند پرداخت کند.

یکی از مسائل مورد توجه ریاضی‌دانان، چگونگی توزیع و ترتیب قرارگرفتن اعداد اول درون رشته اعداد طبیعی است. این چگونگی دارای الگوهایی است که یکی از آنها به «الگوی پیشرفت عددی» معروف است.
مثلاً اگر به عدد ۵ که عددی اول است، ۶ واحد اضافه کنیم به ۱۱ و اگر به ۱۱، ۶ واحد اضافه کنیم به ۱۷ و اگر دوباره اضافه کنیم، به ۲۳ و ۲۹ می‌رسیم که همگی اعدادی اولند. اما با اضافه کردن ۶ واحد دیگر به ۳۵ می‌رسیم که عددی اول نیست و الگو متوقف می‌گردد.

مسئله مورد توجه اینست که در هر الگوی پیشرفت چند عدد اول پیش از رسیدن به اولین عدد غیر اول، بدست می‌آیند؟ طولانی‌ترین رشته‌ای که تاکنون بدست آمده، ۲۲ عدد اول را شامل است. اولین عدد اول این رشته ۱۱۴۱۰۳۳۷۸۵۰۵۵۳ بوده که اگر عدد ۴۶۰۹۰۹۸۶۹۴۲۰۰ به آن اضافه شود عدد اول بعدی به‌وجود می‌آید و می‌توان ۲۲ بار عدد مذکور را به اعداد اول مرحله قبل افزود و عدد اولی جدید بدست آورد. دو ریاضی‌دان اثبات کرده‌اند برای هر رشته از اعداد اول می‌توان به یک رشته عددی رسید.[۸]

0