➗بررسی اول بودن

اول بودن چیست

عدد اول عددی صحیح ۲ یا بزرگ‌تر است که هیچ مقسوم‌علیه غیر از ۱ و خود عدد ندارد. اعدادی مثل ۲ و ۳ و ۵ و ۷ و ۱۱ اول هستند و ۲ تنها عدد اول زوج است.

آیا ۱ عدد اول است

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

نحوه تشخیص اعداد اول

برای بررسی اینکه آیا عدد صحیح n اول است، می‌توان آن را بر اعداد کوچک‌تر یا مساوی √n نسبت به‌ترتیب تقسیم کرد و اگر بر هیچ‌کدام بخش‌پذیر نباشد، عدد اول است. برای مثال ۹۱ بر ۷ بخش‌پذیر است (که کوچک‌تر یا مساوی √۹۱ ≈ ۹.۵ است) پس اول نیست.

• روش تقسیم آزمایشی：روش تقسیم آزمایشی با تقسیم n بر اعداد ۲ تا √n به‌ترتیب برای یافتن مقسوم‌علیه انجام می‌شود و برای اعداد بزرگ‌تر، تعداد تقسیم‌ها بسیار زیاد می‌شود.
• روش بررسی میلر-رابین：روش بررسی میلر-رابین با بررسی باقی‌مانده توان‌هایی برای مبناهای مختلف، شواهدی برای نبودن اول بودن یافت می‌کند و برای اعداد بزرگ نیز سریع عمل می‌کند.