پیدا کردن اعداد اول در برنامه نویسی!

در این آموزش قراره باهم یاد بگیریم چطور میتونیم اعداد اول رو در زبان ها پایتون ، سی پلاس پلاس و سی شارپ پیدا کنیم 🙂

بی مقدمه بریم سراغش لتس گو :

خب اول بیاید ببنیم اعداد اول چیا هستن: طبق تعریف ویکی پدیا از اعداد اول عددی طبیعی (۱، ۲، ۳، …) را «عدد اول» (یا اول) نامند اگر بزرگ‌تر از ۱ بوده و نتوان آن را به‌صورت ضرب دو عدد طبیعی کوچک‌تر نوشت. اعداد بزرگ‌تر از ۱ که اول نباشند را مرکب می‌نامند.

پس با این حساب بیاید اول یه برنامه ساده با پایتون بنویسیم که اعداد اول رو پیدا میکنه بعد همونو با سی پلاس پلاس بنویسیم 🙂

adad = int(input("Enter a number: "))

check= False

if adad > 1:
    for i in range(2, adad):
        if (adad % i) == 0:
            check = True
            break

if check:
    print(adad, "is not a prime number")
else:
    print(adad, "is a prime number")

در کد بالا  ابتدا متغییری وجود دارد که از کاربر عددی را دریافت می کند. ( متغییر adad). سپس فلگی وجود دارد که در ابتدا مقدار آن برابر با FALSE می باشد. تا اینجا اتفاق خاصی نیوفتاده! منطق برنامه از اینجا تعیین میشه: ما یه شرط تعیین کردیم که در اون اگر عددی که کاربر وارد کرده بیشتر از یک باشه، می ره وارد خط های بعدی میشه تا چکش کنیم که اول هست یا نه. در نتیجه میایم اعداد رو از 2 که اولین عدد اوله تا مقدار عددی که کاربر داده بررسی میکنیم. طبق شرط 

if (adad % i) == 0:

اگر عددی که کاربر وارد کرده تقسیم بر عددی بشه ( باقی موندش بر مجموعه اعداد بررسی شده برابر صفر بشه)، فلگ ما مقدار TRUE رو بر میگردونه یعنی حالت اون تغییر میکنه و عدد ما اول نیست! و برنامه پایان می یابه و از حلقه محاسبات خارج میشه.

حالا چطور اعداد اول بین یک بازه رو پیدا کنیم؟

خب اینم کار آسونیه!

به کد زیر دقت کن تا راحت توضیحش بدم :

def calcute(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

start = int(input("enter first number:: "))
end = int(input("Enter secend number: "))

for num in range(start, end+1):
    if calcute(num):
        print(num)

در کد بالا یک تابع وجود داره که اول یک شرط رو بررسی میکنه. اینکه عدد ما (num) اگر زیر 2 باشد یعنی یا 1 یا 0 یا اعداد منفی است که در این صورت اول نیست پس در نتیجه FALSE را بر میگرداند. بعد یک حلقه که اعداد 2 تا مجذور اون عدد رو بررسی میکنه. چون اگر عددی بر توان 2 باقی مونده نداشته باشه میتونه اول باشه. هدف این حلقه از 2 تا جذر مربعی از num بررسی کردن تقسیم پذیری num توسط این اعداده. اگر num تقسیم پذیر باشه توسط یکی از این اعداد، یعنی عددی وجود داره که بتونیم num رو به اون تقسیم کنیم و بدون باقی مانده در نتیجه num اول نیست! سادش کنم: ببین اول باید اعداد بیشتر از 1 رو برداریم و سواشون کنیم تا از اونا بتونیم عدد اول رو بکشیم بیرون. بعد باید یه حلقه داشته باشیم که بیاد این کار رو برامون انجام بده ولی یه شرط هم لازمه. چون عدد اول، عددیه که فقط به خودش و 1 بخش پذیره پس نباید به عدد دیگه ای بخش پذیر باشه. باقی خط هم که تعاریف دریافت عدد از کاربر و حلقه محاسبه هست.

شما فقط کافیه منطق پشت کد رو بفهمید تا بتونید خیلی راحت اونو به زبان های سی پلاس پلاس یا سی شارپ بنویسید. فقط منطق بررسی کننده for و شرط if رو باید درک کنید!

با توجه به چیزی که گفته شد در زبان سی داریم:

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool calculator(int num) {
    if (num < 2)
        return false;
    for (int i = 2; i <= sqrt(num; i++) {
        if (num % i == 0)
            return false;
    }
    return true;
}

int main() {
    int start, end;

    printf("Enter first number: ");
    scanf("%d", &start);
    printf("Enter secend number: ");
    scanf("%d", &end);

    for (int num = start; num <= end; num++) {
        if (calculator(num))
            printf("%d\n", num);
    }

    return 0;
}

همین منطق در زبان سی شارپ:

using System;

namespace Calculator
{
    class Program
    {
        static bool IsPrime(int num)
        {
            if (num < 2)
                return false;
            for (int i = 2; i <= Math.Sqrt(num); i++)
            {
                if (num % i == 0)
                    return false;
            }
            return true;
        }

        static void Main(string[] args)
        {
            int start, end;

            Console.Write("Enter first number: ");
            start = Convert.ToInt32(Console.ReadLine());
            Console.Write("Enter second number: ");
            end = Convert.ToInt32(Console.ReadLine());

            for (int num = start; num <= end; num++)
            {
                if (IsPrime(num))
                    Console.WriteLine(num);
            }
        }
    }
}

جمع بندی

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