در این مقاله از آموزش‌های پی‌استور می‌خواهیم درمورد الگوریتم تشخیص عدد اول و روش‌های تشخیص اعداد اول صحبت کنیم. پیدا کردن اعداد اول با انجام تقسیم‌های متوالی بسیار ساده است، اما اگر بخواهیم عددی بزرگ را بررسی کنیم که اول است یا خیر، به زمان بیشتری نیاز خواهیم داشت و این روش بهینه نخواهد بود. بنابراین از روش‌های دیگر برای این کار بایستی استفاده کنیم که در ادامه مقاله به آن‌ها خواهیم پرداخت.
مقدمه
اعداد اول یکی از بنیادی‌ترین مفاهیم در تاریخچه ریاضی و نظریه اعداد محسوب می‌شوند. یک عدد صحیح بزرگتر از ۱ زمانی اول نامیده می‌شود که فقط بر خودش و عدد ۱ بخش‌پذیر باشد. از دیرباز، دانشمندان و ریاضی‌دانان به مطالعه اعداد اول پرداخته‌اند، زیرا این اعداد نقشی کلیدی در حوزه‌هایی مانند رمزنگاری، امنیت داده‌ها، علوم کامپیوتر، و الگوریتم‌های عددی دارند.
یکی از مسائل مهم در ریاضیات و علوم کامپیوتر، تشخیص عدد اول بودن یک عدد است. به عبارت دیگر، آیا می‌توان به‌طور کارآمد تعیین کرد که یک عدد خاص اول است یا خیر؟ این مسئله نه‌تنها از نظر تئوری جالب است، بلکه در عمل نیز کاربردهای گسترده‌ای دارد. برای مثال، بسیاری از الگوریتم‌های رمزنگاری مانند RSA به اعداد اول بزرگ متکی هستند و کارایی آن‌ها وابسته به سرعت و دقت الگوریتم‌های تشخیص عدد اول است.
تعریف عدد اول
عدد اول، عددی طبیعی بزرگتر از ۱ است که تنها دو مقسوم‌علیه دارد: ۱ و خودش. یعنی نمی‌توان آن را به جز این دو مقدار، بر عدد دیگری بدون باقی‌مانده تقسیم کرد.
اعداد طبیعی شامل اعداد صحیح مثبت مانند ۱، ۱، ۲۰۱، ۲۲۹۹۹۹ و … هستند. اعداد منفی، صفر، اعشار و کسرها جزو اعداد طبیعی محسوب نمی‌شوند. برای مثال:
- عدد ۵ اول است، زیرا فقط بر ۱ و ۵ بخش‌پذیر است.
- عدد ۴ اول نیست، زیرا علاوه بر ۱ و ۴، بر ۲ × ۲ نیز بخش‌پذیر است.
- عدد ۲۰ اول نیست، زیرا علاوه بر ۱ و ۲۰، بر ۲ × ۱۰ و ۴ × ۵ نیز تقسیم می‌شود.
ویژگی‌های مهم اعداد اول
- یکی از سریع‌ترین الگوریتم تشخیص عدد اول این است که بررسی کنیم آیا عدد زوج است یا خیر. اگر عددی بر ۲ بخش‌پذیر باشد، دیگر یک عدد اول نخواهد بود (به‌جز خود عدد ۲ که تنها عدد اول زوج است)
- هیچ عدد اولی، به جز ۲ و ۳، بر ۲ یا ۳ بخش‌پذیر نیست.
- اعداد اول بی‌نهایتند. اقلیدس (ریاضی‌دان یونانی) اثبات کرد که تعداد اعداد اول نامحدود است.
- هر عدد طبیعی بزرگتر از ۱ را می‌توان به صورت ضربی از اعداد اول نوشت. این خاصیت به عنوان قضیه اساسی حساب شناخته می‌شود.
اعداد مرکب
به جز ۱ و اعداد اول، سایر اعداد طبیعی مرکب نامیده می‌شوند. اعداد مرکب، حداقل یک مقسوم‌علیه غیر از ۱ و خودشان دارند. مثال: ۴، ۶، ۸، ۹، ۱۰، ۱۲، …
چرا اعداد اول مهم هستند؟
اعداد اول پایه و اساس نظریه اعداد و بسیاری از کاربردهای مدرن مانند رمزنگاری (مانند RSA)، تولید اعداد تصادفی، و فشرده‌سازی داده‌ها هستند. به همین دلیل، تشخیص عدد اول بودن یک عدد از مسائل مهم در ریاضیات و علوم کامپیوتر محسوب می‌شود.
فلوچارت و الگوریتم تشخیص عدد اول
همانطور که دانستیم، یک عدد اول به عددی بزرگتر از ۱ گفته می‌شود که تنها بر ۱ و خودش بخش‌پذیر باشد. یکی از روش‌های بررسی اول بودن یک عدد، پیاده‌سازی الگوریتمی است که بتواند تعیین کند آیا عدد ورودی تنها بر ۱ و خودش بخش‌پذیر است یا خیر. در این بخش، الگوریتمی نوشته می‌شود که این الگوریتم با بررسی مقسوم‌علیه‌های ممکن یک عدد و استفاده از شرایط خاصی، کارایی مناسبی در تشخیص اعداد اول ارائه می‌دهد.
فلوچارت این الگوریتم به صورت زیر می‌باشد:
این فلوچارت بررسی می‌کند آیا یک عدد اول است یا نه. توضیح مراحل الگوریتم تشخیص عدد اول به شرح زیر است:
- شروع: الگوریتم با دریافت یک عدد (n) آغاز می‌شود.
- بررسی عدد صحیح بودن مقدار ورودی:
- اگر مقدار ورودی یک عدد صحیح نیست، برنامه اعلام می‌کند که اعداد اول باید اعداد صحیح بزرگتر از ۱ باشند و مقدار “خیر” (No) را برمی‌گرداند.
- اگر عدد صحیح باشد، به مرحله بعد می‌رویم.
- بررسی مقدار ورودی:
- اگر عدد ورودی کوچکتر از ۲ باشد (یعنی ۰ یا ۱ باشد)، چون اعداد اول بزرگتر از ۱ هستند، مقدار “خیر” (No) را برمی‌گرداند.
- در غیر این صورت، ادامه می‌دهد.
- مقداردهی اولیه: مقدار متغیر i برابر ۲ قرار داده می‌شود.
- بررسی مقدار i در مقایسه با عدد ورودی:
- اگر مقدار i از مقدار عدد ورودی بزرگتر یا مساوی باشد، پس عدد ورودی یک عدد اول است و مقدار “بله” (Yes) را برمی‌گرداند.
- تقسیم عدد ورودی بر i:
- بررسی می‌کند که آیا عدد ورودی بر i بخش‌پذیر است یا نه.
- بررسی باقی‌مانده تقسیم:
- اگر باقی‌مانده صفر باشد، یعنی عدد ورودی بر i بدون باقی‌مانده تقسیم شده است، در نتیجه عدد اول نیست و مقدار “خیر” (No) را برمی‌گرداند.
- اگر باقی‌مانده صفر نباشد، مقدار i یک واحد افزایش می‌یابد و برنامه به مرحله ۵ بازمی‌گردد تا بررسی را ادامه دهد.
در نهایت، اگر هیچ مقسومی برای عدد پیدا نشود، عدد به عنوان عدد اول تشخیص داده شده و مقدار “بله” (Yes) برگردانده می‌شود.
مثال: اگر عدد ۲۹ را در این فلوچارت آزمایش کنیم، مراحل اجرای الگوریتم به این صورت خواهد بود:
- آیا ۲۹ یک عدد صحیح است؟
- بله ادامه بده.
- آیا ۲۹ کوچکتر یا مساوی ۱ است؟
- خیر ادامه بده.
- مقداردهی اولیه: i = 2
- بررسی آیا i ≥ ۲۹؟
- خیر، پس ادامه بده.
- بررسی بخش‌پذیری ۲۹ بر i (شروع از i = 2):
- ۲۹÷۲=۱۴.۵ (باقی‌مانده دارد) → افزایش i به ۳
- ۲۹÷۳=۹.۶۷ (باقی‌مانده دارد) → افزایش i به ۴
- ۲۹÷۴=۷.۲۵ (باقی‌مانده دارد) → افزایش i به ۵
- ۲۹÷۵=۵.۸ (باقی‌مانده دارد) → افزایش i به ۶
- ۲۹÷۶=۴.۸۳ (باقی‌مانده دارد) → افزایش i به ۷
- … این روند ادامه دارد تا زمانی که i به ۲۹ برسد.
- زمانی که i = 29، شرط i ≥ ۲۹ برقرار می‌شود، پس عدد اول است.
- برگرداندن مقدار “بله” (۲۹ عدد اول است).
روش‌های تشخیص اعداد اول
روش‌های مختلفی برای تشخیص عدد اول و الگوریتم تشخیص عدد اول وجود دارد. برخی از این روش‌های کارآمد هستند و برخی به دلیل کندی سرعت ناکارآمد هستند و در اعداد بزرگتر پاسخ نمی‌دهند. در ادامه به انواع این روش‌ها اشاره می‌کنیم:
۱- روش بررسی مقسوم‌علیه‌ها (تقسیم بر همه‌ی اعداد کوچکتر از خودش)
در این روش، عدد را بر تمام اعداد از ۲ تا خودش منهای یک (n-1) تقسیم می‌کنیم. اگر بر هیچ‌کدام بخش‌پذیر نبود، عدد اول است. این روش ساده‌ترین ولی کندترین روش برای تشخیص اعداد اول است، زیرا تعداد زیادی عملیات تقسیم انجام می‌شود.
مراحل:
- اگر عدد کوچکتر یا مساوی ۱ باشد، عدد اول نیست.
- از عدد ۲ تا n-1 بررسی کنید:
- اگر عدد بر هرکدام بخش‌پذیر باشد، اول نیست.
- اگر هیچ بخش‌پذیری پیدا نشد، عدد اول است.
مثال: بررسی عدد ۷
- تقسیم بر ۲ → باقی‌مانده دارد
- تقسیم بر ۳ → باقی‌مانده دارد
- تقسیم بر ۴، ۵، ۶ → باقی‌مانده دارد
- چون بر هیچ عددی جز ۱ و خودش بخش‌پذیر نیست، ۷ عدد اول است.
پیاده سازی الگوریتم تشخیص عدد اول با روش بررسی مقسوم‌علیه‌ها
در کد زیر از روش ساده (بررسی همه‌ی مقسوم‌علیه‌ها) برای تشخیص اعداد اول استفاده می‌شود. در این الگوریتم، عدد n را از ۲ تا n-1 بررسی می‌کند و اگر n بر هیچ‌کدام از این اعداد بخش‌پذیر نباشد، آن را عدد اول در نظر می‌گیرد.
- پیاده سازی به زبان پایتون
def isPrime(n):
if n <= 1:
return False
# Check divisibility from 2 to n-1
for i in range(2, n):
if n % i == 0:
return False
return True
if __name__ == "__main__":
n = 11
if(isPrime(n)):
print("true")
else:
print("false")
- پیاده سازی به زبان سی پلاس پلاس
#include <iostream>
using namespace std;
bool isPrime(int n) {
if (n <= 1)
return false;
// Check divisibility from 2 to n-1
for (int i = 2; i < n; i++)
if (n % i == 0)
return false;
return true;
}
int main() {
int n = 11;
if(isPrime) cout << "true";
else cout<<"false";
return 0;
}
- پیاده سازی به زبان سی شارپ
using System;
class GfG {
static bool IsPrime(int n) {
if (n <= 1)
return false;
// Check divisibility from 2 to n-1
for (int i = 2; i < n; i++)
if (n % i == 0)
return false;
return true;
}
static void Main(string[] args) {
int n = 11;
if(IsPrime(n))
Console.WriteLine("true");
else
Console.WriteLine("false");
}
}
- پیاده سازی به زبان جاوا
class GfG {
static boolean isPrime(int n) {
if (n <= 1)
return false;
// Check divisibility from 2 to n-1
for (int i = 2; i < n; i++)
if (n % i == 0)
return false;
return true;
}
public static void main(String[] args) {
int n = 11;
if(isPrime(n)){
System.out.println("true");
}else{
System.out.println("false");
}
}
}
۲- روش ریشه‌ی دوم (تقسیم تا ریشه‌ی دوم عدد)
این روش یک بهبود مهم نسبت به روش قبل است. به جای بررسی همه‌ی اعداد، فقط اعداد کوچکتر یا مساوی ریشه‌ی دوم عدد بررسی می‌شوند. دلیل این کار این است که اگر عددی مقسوم‌علیه داشته باشد، یکی از آن‌ها کوچکتر یا مساوی ریشه‌ی دوم عدد خواهد بود. این روش سرعت بیشتری دارد و تعداد تقسیم‌ها را کاهش می‌دهد.
مراحل:
- اگر عدد کوچکتر یا مساوی ۱ باشد، عدد اول نیست.
- اگر عدد ۲ یا ۳ باشد، عدد اول است.
- از ۲ تا ریشه‌ی دوم عدد بررسی کنید:
- اگر عدد بر هرکدام بخش‌پذیر باشد، اول نیست.
- در غیر این صورت، اول است.
مثال: بررسی عدد ۲۹
- ریشه‌ی دوم ۲۹ ≈ ۵.۳ → فقط تا عدد ۵ بررسی می‌کنیم.
- ۲۹ تقسیم بر ۲، ۳، ۴، ۵ → باقی‌مانده دارد.
- چون بر هیچ‌کدام بخش‌پذیر نیست، ۲۹ عدد اول است.
پیاده سازی الگوریتم تشخیص عدد اول با روش ریشه‌ی دوم
در کد زیر از روش بهینه‌تر (بررسی جذر n به عنوان محدودیت) برای تشخیص اعداد اول استفاده می‌شود. در این الگوریتم، به جای بررسی تمام اعداد از ۲ تا n-1، تنها تا جذر n بررسی می‌کند، و اگر هیچ مقسوم‌علیه‌ای پیدا نشد، عدد اول است.
- پیاده سازی به زبان پایتون
import math
def isPrime(n):
# Numbers less than or equal to 1 are not prime
if n <= 1:
return False
# Check divisibility from 2 to the square root of n
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
# If no divisors were found, n is prime
return True
if __name__ == "__main__":
n = 11
if(isPrime(n)):
print("true")
else:
print("false")
- پیاده سازی به زبان سی پلاس پلاس
#include <iostream>
#include <cmath>
using namespace std;
// Function to check whether a number is prime or not
bool isPrime(int n) {
// Numbers less than or equal to 1 are not prime
if (n <= 1)
return false;
// Check divisibility from 2 to the square root of n
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0)
return false;
// If no divisors were found, n is prime
return true;
}
int main() {
int n = 11;
if(isPrime) cout << "true";
else cout<<"false";
return 0;
}
- پیاده سازی به زبان سی شارپ
using System;
class GfG {
static bool IsPrime(int n) {
// Numbers less than or equal to 1 are not prime
if (n <= 1)
return false;
// Check divisibility from 2 to the square root of n
for (int i = 2; i <= Math.Sqrt(n); i++)
if (n % i == 0)
return false;
// If no divisors were found, n is prime
return true;
}
static void Main(string[] args) {
int n = 11;
if(IsPrime(n))
Console.WriteLine("true");
else
Console.WriteLine("false");
}
}
- پیاده سازی به زبان جاوا
class GfG {
static boolean isPrime(int n) {
// Numbers less than or equal to 1 are not prime
if (n <= 1)
return false;
// Check divisibility from 2 to the square root of n
for (int i = 2; i <= Math.sqrt(n); i++)
if (n % i == 0)
return false;
// If no divisors were found, n is prime
return true;
}
public static void main(String[] args) {
int n = 11;
if(isPrime(n)){
System.out.println("true");
}else{
System.out.println("false");
}
}
}
۳- روش 6k ± ۱ (بررسی بخش‌پذیری بر ۲ و ۳ و اعداد خاص)
اعداد اول (به جز ۲ و ۳) در قالب 6k ± ۱ ظاهر می‌شوند. این یعنی هر عدد اولی باید یا ۱ واحد از مضرب ۶ بیشتر باشد (6k+1) یا ۵ واحد از مضرب ۶ بیشتر باشد (6k+5). بنابراین، به جای بررسی همه‌ی اعداد، فقط اعدادی که در این الگو هستند بررسی می‌شوند. این روش تقسیم‌های غیرضروری را کاهش می‌دهد و بسیار سریع است.
مراحل:
- چک کردن برای اعداد کمتر از یا مساوی ۱: اگر n کوچکتر یا مساوی ۱ باشد، عدد اول نیست.
- چک کردن برای اعداد ۲ و ۳: اگر n برابر با ۲ یا ۳ باشد، این عدد اول است.
- چک کردن تقسیم‌پذیری بر ۲ یا ۳: اگر n بر ۲ یا ۳ بخش‌پذیر باشد، عدد اول نیست.
- بررسی اعداد از ۵ به بعد (با گام‌های ۶):
- از ۵ شروع می‌کند و به ترتیب اعداد ۵، ۷، ۱۱، ۱۳، ۱۷ و… را بررسی می‌کند (این اعداد در قالب 6k ± ۱ هستند).
- از آنجا که اعداد 6k، 6k+2، 6k+3، و 6k+4 از قبل بررسی شده‌اند (مقسوم‌علیه‌هایی هستند که بر ۲ یا ۳ بخش‌پذیرند)، به بررسی تنها اعداد 6k+1 و 6k+5 می‌پردازد.
- اگر n بر یکی از این اعداد بخش‌پذیر باشد، عدد اول نیست.
- اگر هیچ مقسوم‌علیه‌ای پیدا نشد، n عدد اول است.
مثال: بررسی عدد ۳۷
- ۳۷ بر ۲ و ۳ بخش‌پذیر نیست.
- ریشه‌ی دوم ۳۷ ≈ ۶.۰۸ → فقط تا ۶ بررسی می‌کنیم.
- عددهای 6k ± ۱ تا ۶: ۵ و ۷
- ۳۷ بر ۵ و ۷ بخش‌پذیر نیست.
- پس ۳۷ عدد اول است.
پیاده سازی الگوریتم تشخیص عدد اول با روش 6k ± ۱
در کد زیر از روش سریع‌تر و بهینه‌تر (کاهش تعداد تقسیم‌ها) برای تشخیص اعداد اول استفاده می‌شود. این الگوریتم شامل بررسی اعداد از ۵ به بعد با گام‌های ۶ است. در این روش، به طور خاص، تنها اعدادی که در قالب 6k ± ۱ هستند بررسی می‌شوند (به جای بررسی تمام اعداد فرد).
- پیاده سازی به زبان پایتون
import math
def isPrime(n):
# Check if n is 1 or 0
if n <= 1:
return False
# Check if n is 2 or 3
if n == 2 or n == 3:
return True
# Check whether n is divisible by 2 or 3
if n % 2 == 0 or n % 3 == 0:
return False
# Check from 5 to square root of n
# Iterate i by (i+6)
i = 5
while i <= math.sqrt(n):
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
if __name__ == "__main__":
n = 11
if(isPrime(n)):
print("true")
else:
print("false")
- پیاده سازی به زبان سی پلاس پلاس
#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int n) {
// Check if n is 1 or 0
if (n <= 1)
return false;
// Check if n is 2 or 3
if (n == 2 || n == 3)
return true;
// Check whether n is divisible by 2 or 3
if (n % 2 == 0 || n % 3 == 0)
return false;
// Check from 5 to square root of n
// Iterate i by (i+6)
for (int i = 5; i <= sqrt(n); i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
int main() {
int n = 11;
if(isPrime) cout << "true";
else cout<<"false";
return 0;
}
- پیاده سازی به زبان سی شارپ
using System;
class GfG {
static bool IsPrime(int n) {
// Check if n is 1 or 0
if (n <= 1)
return false;
// Check if n is 2 or 3
if (n == 2 || n == 3)
return true;
// Check whether n is divisible by 2 or 3
if (n % 2 == 0 || n % 3 == 0)
return false;
// Check from 5 to square root of n
// Iterate i by (i+6)
for (int i = 5; i <= Math.Sqrt(n); i += 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
static void Main(string[] args) {
int n = 11;
if(IsPrime(n))
Console.WriteLine("true");
else
Console.WriteLine("false");
}
}
- پیاده سازی به زبان جاوا
class GfG {
static boolean isPrime(int n) {
// Check if n is 1 or 0
if (n <= 1)
return false;
// Check if n is 2 or 3
if (n == 2 || n == 3)
return true;
// Check whether n is divisible by 2 or 3
if (n % 2 == 0 || n % 3 == 0)
return false;
// Check from 5 to square root of n
// Iterate i by (i+6)
for (int i = 5; i <= Math.sqrt(n); i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
public static void main(String[] args) {
int n = 11;
if(isPrime(n)){
System.out.println("true");
}else{
System.out.println("false");
}
}
}
۴- روش غربال اراتوستن (پیدا کردن چندین عدد اول با هم)
اگر بخواهید همه‌ی اعداد اول تا عددی مشخص را پیدا کنید، روش غربال اراتوستن بسیار سریع و کارآمد است. در این روش، از کوچک‌ترین عدد اول شروع کرده و مضرب‌های آن را حذف می‌کنیم تا در نهایت، فقط اعداد اول باقی بمانند. این روش یکی از سریع‌ترین روش‌ها برای پیدا کردن تعداد زیادی عدد اول است.
مراحل:
- ساخت لیستی از اعداد: لیستی از اعداد از ۲ تا n را در نظر بگیرید.
- شروع از ۲: از عدد ۲ شروع کنید که اولین عدد اول است.
- تمام مضارب ۲ (مانند ۴، ۶، ۸، …) را از لیست حذف کنید، زیرا همه این‌ها قابل تقسیم بر ۲ هستند و بنابراین اول نیستند.
- انتقال به عدد بعدی که حذف نشده است: به عدد بعدی که هنوز از لیست حذف نشده (مثلاً ۳) برسید و مضارب آن را حذف کنید (مانند ۹، ۱۲، ۱۵، …).
- ادامه تا جذر n: این فرآیند را برای هر عدد تا ریشه‌ی دوم n ادامه دهید.
- چون وقتی به عددی برسید که بزرگتر از جذر n است، تمام مضارب آن قبلاً حذف شده‌اند.
- اعداد باقی‌مانده: در نهایت، تمام اعدادی که هنوز از لیست حذف نشده‌اند، اعداد اول هستند.
مثال: پیدا کردن اعداد اول تا ۳۰
- لیست اولیه: 2, ۳, ۴, ۵, ۶, ۷, ۸, ۹, …, ۳۰
- حذف مضارب ۲: 2, ۳, ۵, ۷, ۹, ۱۱, ۱۳, …
- حذف مضارب ۳: 2, ۳, ۵, ۷, ۱۱, ۱۳, ۱۷, …
- حذف مضارب ۵ و ۷: 2, ۳, ۵, ۷, ۱۱, ۱۳, ۱۷, ۱۹, ۲۳, ۲۹
- اعداد باقی‌مانده، اعداد اول هستند.
پیاده سازی الگوریتم تشخیص عدد اول با روش غربال اراتوستن
در کد زیر از یک روش قدیمی (حذف اعدادی که بر اعداد دیگر تقسیم می‌شوند) برای تشخیص اعداد اول استفاده می‌شود. این الگوریتم از این ایده استفاده می‌کند که اگر یک عدد اول را پیدا کنیم، تمام مضارب آن را می‌توان حذف کرد زیرا آن‌ها دیگر اول نخواهند بود.
- پیاده سازی به زبان پایتون
# Python program to print all
# primes smaller than or equal to
# n using Sieve of Eratosthenes
def SieveOfEratosthenes(n):
# Create a boolean array
# "prime[0..n]" and initialize
# all entries it as true.
# A value in prime[i] will
# finally be false if i is
# Not a prime, else true.
prime = [True for i in range(n+1)]
p = 2
while (p * p <= n):
# If prime[p] is not
# changed, then it is a prime
if (prime[p] == True):
# Update all multiples of p
for i in range(p * p, n+1, p):
prime[i] = False
p += 1
# Print all prime numbers
for p in range(2, n+1):
if prime[p]:
print(p)
# Driver code
if __name__ == '__main__':
n = 30
print("Following are the prime numbers smaller"),
print("than or equal to", n)
SieveOfEratosthenes(n)
- پیاده سازی به زبان سی پلاس پلاس
// C++ program to print all primes smaller than or equal to
// n using Sieve of Eratosthenes
#include <bits/stdc++.h>
using namespace std;
void SieveOfEratosthenes(int n)
{
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
vector<bool> prime(n + 1, true);
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not c
hanged, then it is a prime
if (prime[p] == true) {
// Update all multiples of p greater than or
// equal to the square of it numbers which are
// multiple of p and are less than p^2 are
// already been marked.
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
// Print all prime numbers
for (int p = 2; p <= n; p++)
if (prime[p])
cout << p << " ";
}
// Driver Code
int main()
{
int n = 30;
cout << "Following are the prime numbers smaller "
<< " than or equal to " << n << endl;
SieveOfEratosthenes(n);
return 0;
}
پیاده سازی به زبان سی شارپ
// C# program to print all primes
// smaller than or equal to n
// using Sieve of Eratosthenes
using System;
namespace prime {
public class GFG {
public static void SieveOfEratosthenes(int n)
{
// Create a boolean array
// "prime[0..n]" and
// initialize all entries
// it as true. A value in
// prime[i] will finally be
// false if i is Not a
// prime, else true.
bool[] prime = new bool[n + 1];
for (int i = 0; i <= n; i++)
prime[i] = true;
for (int p = 2; p * p <= n; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
// Print all prime numbers
for (int i = 2; i <= n; i++)
{
if (prime[i] == true)
Console.Write(i + " ");
}
}
// Driver Code
public static void Main()
{
int n = 30;
Console.WriteLine(
"Following are the prime numbers");
Console.WriteLine("smaller than or equal to " + n);
SieveOfEratosthenes(n);
}
}
}
- پیاده سازی به زبان جاوا
// Java program to print all primes smaller than or equal to
// n using Sieve of Eratosthenes
class SieveOfEratosthenes {
void sieveOfEratosthenes(int n)
{
// Create a boolean array "prime[0..n]" and
// initialize all entries it as true. A value in
// prime[i] will finally be false if i is Not a
// prime, else true.
boolean prime[] = new boolean[n + 1];
for (int i = 0; i <= n; i++)
prime[i] = true;
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed, then it is a
// prime
if (prime[p] == true) {
// Update all multiples of p greater than or
// equal to the square of it numbers which
// are multiple of p and are less than p^2
// are already been marked.
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
// Print all prime numbers
for (int i = 2; i <= n; i++) {
if (prime[i] == true)
System.out.print(i + " ");
}
}
// Driver Code
public static void main(String args[])
{
int n = 30;
System.out.print("Following are the prime numbers ");
System.out.println("smaller than or equal to " + n);
SieveOfEratosthenes g = new SieveOfEratosthenes();
g.sieveOfEratosthenes(n);
}
}
- پیاده سازی به زبان پی اچ پی
<?php
// php program to print all primes smaller
// than or equal to n using Sieve of
// Eratosthenes
function SieveOfEratosthenes($n)
{
// Create a boolean array "prime[0..n]"
// and initialize all entries it as true.
// A value in prime[i] will finally be
// false if i is Not a prime, else true.
$prime = array_fill(0, $n+1, true);
for ($p = 2; $p*$p <= $n; $p++)
{
// If prime[p] is not changed,
// then it is a prime
if ($prime[$p] == true)
{
// Update all multiples of p
for ($i = $p*$p; $i <= $n; $i += $p)
$prime[$i] = false;
}
}
// Print all prime numbers
for ($p = 2; $p <= $n; $p++)
if ($prime[$p])
echo $p." ";
}
// Driver Code
$n = 30;
echo "Following are the prime numbers "
."smaller than or equal to " .$n."\n" ;
SieveOfEratosthenes($n);
?>
کاربردهای عدد اول
همانطور که دانستیم، با الگوریتم تشخیص عدد اول می‌توانیم بررسی کنیم عددی اول است یا خیر. اما این اعداد چه کاربردی دارند؟ اعداد اول در علوم مختلف، مهندسی، امنیت اطلاعات و حتی طبیعت نقش بسیار مهمی دارند. در ادامه به برخی از مهم‌ترین کاربردهای عدد اول می‌پردازیم:
۱- رمزنگاری و امنیت اطلاعات
الگوریتم‌های رمزنگاری مانند RSA از اعداد اول برای ایجاد کلیدهای امن استفاده می‌کنند. دلیل اصلی استفاده از اعداد اول در رمزنگاری این است که تجزیه‌ی اعداد بزرگ به عوامل اول بسیار دشوار است و رایانه‌های معمولی برای این کار به سال‌ها زمان نیاز دارند.
در امنیت دیجیتال، از اعداد اول برای رمزگذاری داده‌ها، حفاظت از اطلاعات بانکی، تراکنش‌های اینترنتی، و حتی رمزگذاری پیام‌ها در پیام‌رسان‌ها استفاده می‌شود. مثال:
- RSA (Rivest-Shamir-Adleman) یکی از محبوب‌ترین الگوریتم‌های رمزنگاری است که بر اساس ضرب دو عدد اول بسیار بزرگ کار می‌کند.
- HTTPS و SSL/TLS که امنیت سایت‌های اینترنتی را تضمین می‌کنند، از اعداد اول برای رمزنگاری استفاده می‌کنند.
۲- زیست‌شناسی و چرخه‌ی زندگی حشرات
برخی از گونه‌های سیکادا (Cicada) هر ۱۳ یا ۱۷ سال یک‌بار از زمین خارج می‌شوند. دلیل این انتخاب این است که ۱۳ و ۱۷ عدد اول هستند و این باعث می‌شود که شکارچیان آن‌ها نتوانند چرخه‌ی منظمی برای شکارشان ایجاد کنند. این یک استراتژی بقای تکاملی است که احتمال زنده ماندن این حشرات را افزایش می‌دهد.
۳- ریاضیات و نظریه اعداد
اعداد اول، بلوک‌های سازنده‌ی تمام اعداد صحیح هستند. در نظریه اعداد، قضیه‌ی اساسی حساب بیان می‌کند که هر عدد صحیح مثبت را می‌توان به‌صورت یکتایی به حاصل‌ضرب اعداد اول تجزیه کرد.
توابع ریاضی مهمی مانند تابع فی اویلر (Euler’s Totient Function)، تابع زتای ریمان (Riemann Zeta Function)، و الگوریتم غربال اراتوستن برای تولید اعداد اول استفاده می‌شوند.
۴- مهندسی و طراحی چرخ‌دنده‌ها
در صنعت تولید چرخ‌دنده‌ها، تعداد دندانه‌های چرخ‌دنده را عددی اول انتخاب می‌کنند. اگر تعداد دندانه‌های دو چرخ‌دنده‌ی متصل مضرب یکدیگر باشد، یک الگوی فرسایش نامطلوب ایجاد می‌شود که باعث ساییدگی زودهنگام می‌شود. اما اگر تعداد دندانه‌ها عدد اول باشد، فرسایش به‌صورت یکنواخت توزیع می‌شود و طول عمر قطعات افزایش می‌یابد.
۵- فشرده‌سازی داده‌ها و الگوریتم‌های هش
بسیاری از الگوریتم‌های فشرده‌سازی و هش (مانند SHA-256 و MD5) از ویژگی‌های اعداد اول برای ایجاد خروجی‌های یکتا و غیرقابل پیش‌بینی استفاده می‌کنند. از اعداد اول برای بهینه‌سازی جداول در پایگاه‌های داده و جلوگیری از برخوردهای تصادفی در مقادیر هش استفاده می‌شود.
۶- گرافیک کامپیوتری و پردازش تصاویر
در پردازش تصویر و گرافیک کامپیوتری، از اعداد اول برای ایجاد رنگ‌های تصادفی، الگوهای پیچیده، و تنظیم شدت پیکسل‌ها استفاده می‌شود. همچنین در بازی‌های ویدیویی، از اعداد اول برای ایجاد دنباله‌های تصادفی و الگوهای غیرتکراری در محیط بازی‌ها استفاده می‌شود.
۷- کشف سیارات و اخترشناسی
در جستجوی حیات فرازمینی، دانشمندان از دنباله‌های اعداد اول برای ارسال سیگنال‌های رادیویی به فضا استفاده می‌کنند. دلیل این کار این است که اعداد اول در طبیعت نادر هستند و یک الگوی تصادفی ندارند، بنابراین اگر تمدنی بیگانه به این سیگنال‌ها پاسخ دهد، نشان‌دهنده‌ی هوش آن‌ها خواهد بود.
۸- موسیقی
در طراحی ابزارهای موسیقی، از اعداد اول برای کاهش پدیده‌ی تشدید (Resonance) استفاده می‌شود. هنگامی که نت‌ها و فرکانس‌های خاصی بر اساس اعداد اول تنظیم می‌شوند، از ایجاد هارمونی‌های نامطلوب جلوگیری می‌شود.
نتیجه گیری
الگوریتم تشخیص عدد اول از اهمیت بالایی در ریاضیات و علوم کامپیوتر برخوردار است و الگوریتم‌های مختلفی برای این کار توسعه یافته‌اند. از ساده‌ترین روش‌های تقسیم تا بهینه‌ترین روش‌ها با استفاده از ریشه دوم عدد، هر کدام مزایا و معایب خاص خود را دارند. به طور کلی، انتخاب روش مناسب برای تشخیص اعداد اول بستگی به نیاز و مقیاس مسئله دارد؛ اما با توجه به استفاده‌های گسترده‌ای که از اعداد اول در رمزنگاری و سیستم‌های امنیتی می‌شود، فهم و به‌کارگیری این الگوریتم‌ها به‌طور مؤثر اهمیت زیادی دارد.
