برنامه اعداد اول کوچکتر از n در c++

در این نوشته آموزشی کد برنامه چاپ اعداد اول تا n و همچنین الگوریتم شناسایی عدد اول را به زبان های C++ و C بررسی می کنیم.

تعریف ریاضی عدد اول

از دیدگاه ریاضی، یک عدد صحیح که تنها و تنها بر یک و خودش بخش پذیر است به عنوان عدد اول شناخته می شود.

به این ترتیب مثلا عدد 13 یک عدد اول است چرا که به غیر از 1 و 13 بر هیچ عدد دیگری بخش پذیر نیست.

اما عدد 15 عدد اول نیست چرا که علاوه بر 1 و 15 بر 3 و 5 نیز بخش پذیر است.

برای این که بتوانید این تمرین و کد هایی که در ادامه می بینید را متوجه شوید، می بایست با مباحث زیر در زبان های C و C++ آشنا باشید.

• if…if else و if تو در تو
• حلقه for تو در تو
• دستور break و continue

برنامه تشخیص عدد اول در زبان C++

#include <iostream>
using namespace std;

int main() {
    int i, n;
    bool isPrime = true;

    cout << "Enter a positive integer: ";
    cin >> n;

    // 0 and 1 are not prime numbers
    if (n == 0 || n == 1) {
        isPrime = false;
    }
    else {
        for (i = 2; i <= n / 2; ++i) {
            if (n % i == 0) {
                isPrime = false;
                break;
            }
        }
    }
    if (isPrime)
        cout << n << " is a prime number";
    else
        cout << n << " is not a prime number";

    return 0;
}

خروجی

Enter a positive integer: 29

29 is a prime number.

این برنامه یک integer مثبت از کاربر می گیرد و در متغیری به نام n ذخیره می کند.

توجه داشته باشید که متغیر بولین isPrime در ابتدا با مقدار true ساخته می شود.

از آن جایی که 0 و 1 عدد اول نیستند، ابتدا چک می کنیم که آیا عدد ورودی یک از آن اعداد است یا خیر.

در غیر این صورت در حلقه for بررسی می شود که آیا عدد وارد شده بر i هایی که در این حلقه تولید می شوند قابل تقسیم است یا خیر.

for (i = 2; i <= n / 2; ++i) {
    if (n % i == 0) {
        isPrime = false;
        break;
    }
}

توجه داشته باشید که دلیل این که حلقه تا n / 2 پیشروی می کند این است که امکان ندارد که بعد از n / 2 بتوانیم عاملی را پیدا کنیم که عدد n بر آن بخش پذیر باشد بنابراین ادامه دادن بی فایده است.

تشخیص عدد اول در زبان C

#include <stdio.h>
int main() {
    int n, i, flag = 0;
    printf("Enter a positive integer: ");
    scanf("%d", &n);

    for (i = 2; i <= n / 2; ++i) {

        // condition for non-prime
        if (n % i == 0) {
            flag = 1;
            break;
        }
    }

    if (n == 1) {
        printf("1 is neither prime nor composite.");
    }
    else {
        if (flag == 0)
            printf("%d is a prime number.", n);
        else
            printf("%d is not a prime number.", n);
    }

    return 0;
}

خروجی

Enter a positive integer: 29

29 is a prime number.

برنامه چاپ اعداد اول بین دو عدد 2 و کوچکتر از n در زبان C++

#include <iostream>

using namespace std;

int main() {

    int num, i, upto;

    // Take input from user
    cout << "Find prime numbers upto : ";
    cin >> upto;

    cout << endl << "All prime numbers upto " << upto << " are : " << endl;

    for(num = 2; num <= upto; num++) {

        for(i = 2; i <= (num / 2); i++) {

            if(num % i == 0) {
                i = num;
                break;
            }
        }

        // If the number is prime then print it.
        if(i != num) {
            cout << num << " ";
        }
    }

    return 0;
}

خروجی

Find prime numbers upto : 100

All prime numbers upto 100 are :

3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

برای چاپ تمام اعداد اول تا n حلقه را از 2 تا n تعریف می کنیم و سپس داخل حلقه بررسی می کنیم که متغیر num اول است یا خیر.

برای این منظور به یک حلقه دیگر که در واقع می شود حلقه تو در تو نیاز داریم؛ البته که بهینه ترین راه برای پیدا کردن عدد اول نیست ولی برای یادگیری ساده تر آن از این روش استفاده می کنیم.

چاپ اعداد اول بین دو عدد 2 و کوچکتر از n در زبان C

#include <stdio.h>

int main() {
   int low, high, i, flag;
   printf("Enter two numbers(intervals): ");
   scanf("%d %d", &low, &high);
   printf("Prime numbers between %d and %d are: ", low, high);

   // iteration until low is not equal to high
   while (low < high) {
      flag = 0;

      // ignore numbers less than 2
      if (low <= 1) {
         ++low;
         continue;
      }

      // if low is a non-prime number, flag will be 1
      for (i = 2; i <= low / 2; ++i) {

         if (low % i == 0) {
            flag = 1;
            break;
         }
      }

      if (flag == 0)
         printf("%d ", low);

      // to check prime for the next number
      // increase low by 1
      ++low;
   }

   return 0;
}

خروجی

Enter two numbers(intervals): 20

50

Prime numbers between 20 and 50 are: 23 29 31 37 41 43 47

در این کد، حلقه تکرار while به تعداد high-low-1 بار تکرار می شود.

در هر بار تکرار این که آیا low عدد اول است یا خیر مورد بررسی قرار می گیرد و تا زمانی که low برابر با high شود یک واحد به آن در هر بار تکرار اضافه می شود.

توجه داشته باشید که اگر عدد بزرگتر اول وارد شود برنامه بالا کار نمی کند.

اگر می خواهید در حالتی که عدد اول بزرگ تر وارد شد نیز برنامه شما کار کند کافی است تا در کد برنامه با یک دستور if ابتدا بررسی کنید که آیا عدد اول بزرگ تر از عدد دوم است و اگر این طور بود اعداد را جا به جا کنید.

برای دنبال کردن نوشته های کاپ کد به کانال تلگرامی آن (cupcode_ir@) بپیوندید!

برای ثبت سفارش برنامه نویسی، طراحی وب سایت، بهینه سازی و... در کاپ کد کلیک کنید.

منبع: cupcode.ir