عدد اول
عدد اول، عددیست که به جز خودش و یک، مقسوم علیه دیگری ندارد؛ یعنی فقط بر خودش و یک بخش پدیر میباشد!
شرح الگوریتم
این را می‌دانیم که:
- هر عددی، بر یک و خودش بخش پذیر است.
- اگر عدد کوچکتر از 1 باشد، پس 100% عدد اول نیست. (چون فقط یک مقسوم علیه دارد)
- هر عدد بالای 1، حداقل دو مقسوم علیه خواهد داشت و اگر بیشتر از دو تا باشد، پس اول است.
- عدد b در صورتی مقسوم علیه a است که a بر b بخش پذیر باشد! یعنی a تقسیم بر b، باقی‌مانده‌ی صفر داشته باشد.
با این اوصاف، برای تشخیص اول بودن یک عدد در برنامه نویسی:
- ابتدا باید بررسی کنیم که عدد از 1 بزرگتر است یا خیر؛ چون اگر کوچکتر بود، پس قطعا اول نیست.
- شروع به پیدا کردن مقسوم علیه‌های آن عدد می‌کنیم! ولی به چه صورت؟!
از آنجایی که بر 1 و خودش بخش پذیر است، بنابراین از 2 تا یکی کمتر از خود آن عدد شروع به پیدا کردن مقسوم علیه‌ها می‌کنیم. - هرجا که مقسوم علیهی پیدا شد، پس عدد 100% اول نیست؛ چون بیشتر از دو مقسوم علیه دارد و نیازی به پیدا کردن مقسوم علیه‌های دیگر نیست.
ولی اگر چیزی یافت نشد، پس اول است.
پیاده‌سازی
این کد در جاوا و سی‌شارپ پیاده‌سازی شده ست.
1 2 3 4 5 6 7 8 9 10 11 12 13 | boolisFirst(intx) { if(x<=1)returnfalse; inth=1; for(inti=2;i<=x;i++) { if(x%i==0){ h++; if(h>2)returnfalse; } } returntrue; } |
بهینه سازی برای اعداد زوج
اعداد زوج به جز 2، عدد اول نیستند! چرا؟! چون علاوه بر یک و خودشان، بر 2 نیز بخش پذیرند!
بنابراین میتوانید حلقه را به نحوی بنویسید که اعداد زوج را حساب نکند، یعنی اینکه مقدار i، دو واحد دو واحد زیاد شود ولی توجه داشته باشید که این کار را حتما باید از عدد 3 به بعد شروع کرده و عدد 2 را قبل از حلقه نوشته و بررسی کنید.