سورس کد یافتن عدد اول در c/cpp

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

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

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

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

#include <iostream>
using namespace std;
bool prime(int Number);
int main(){
	int num;
	cout << "Enter Number : ";
	cin >> num;
	cin.get();
	if (prime(num))
		cout << num << " is a prime number";
	else
		cout << num << " not a prime number";
	cin.get();
	return 0;
}
bool prime(int Number){
	bool is_prime = true;
	for (int a = 2; a <= (Number / 2); a++) 
		if (Number % a == 0) is_prime = false;	
	return is_prime;
}