BGDCL Sub-Assistant Engineer Exam 19 November 2021 — Question Solution | বাখরাবাদ গ্যাস (বিজিডিসিএল) উপ-সহকারী প্রকৌশলী নিয়োগ পরীক্ষা ২০২১ — প্রশ্ন সমাধান

মৌলিক সংখ্যা (Prime number): ১-এর চেয়ে বড় যে পূর্ণসংখ্যার ১ ও সে নিজে ছাড়া আর কোনো ধনাত্মক উৎপাদক নেই। ০, ১ ও ঋণাত্মক সংখ্যা মৌলিক নয়।

পদ্ধতি: N যৌগিক হলে N = a × b (a ≤ b) লেখা যায়, তখন a ≤ √N। তাই 2 থেকে √N পর্যন্ত কোনো সংখ্যা দিয়ে N বিভাজ্য না হলে N মৌলিক। প্রথম উৎপাদক পেলেই লুপ থামানো হয়।

অ্যালগরিদম

1. N ইনপুট নাও।
2. N < 2 হলে "Prime নয়"।
3. i = 2 থেকে i × i ≤ N পর্যন্ত: N % i = 0 হলে "Prime নয়", থামো।
4. কোনো উৎপাদক না পেলে "Prime"।

প্রোগ্রাম (C)

#include <stdio.h>

int main(void)
{
    int n, i, isPrime = 1;

    printf("Enter N: ");
    if (scanf("%d", &n) != 1) {
        printf("Invalid input\n");
        return 1;
    }

    if (n < 2)
        isPrime = 0;                    /* 0, 1 ও ঋণাত্মক সংখ্যা মৌলিক নয় */
    else
        for (i = 2; i <= n / i; i++)    /* i*i <= n, overflow ছাড়া */
            if (n % i == 0) {
                isPrime = 0;            /* উৎপাদক পাওয়া গেছে */
                break;
            }

    if (isPrime)
        printf("%d is a Prime number\n", n);
    else
        printf("%d is not a Prime number\n", n);
    return 0;
}

নমুনা আউটপুট

Enter N: 17
17 is a Prime number

Enter N: 91
91 is not a Prime number

Enter N: 1
1 is not a Prime number

Enter N: 2
2 is a Prime number

Trace (N = 91): i = 2 → 91 % 2 = 1; i = 3 → 1; i = 4 → 3; i = 5 → 1; i = 6 → 1; i = 7 → 91 % 7 = 0, তাই isPrime = 0 এবং লুপ থামে (91 = 7 × 13)।
Trace (N = 17): i = 2, 3, 4-এ ভাগশেষ শূন্য নয়; i = 5-এ 5 > 17/5 = 3, লুপ শেষ; কোনো উৎপাদক নেই, তাই 17 মৌলিক।

কেন i <= n / i: এটি i × i ≤ n-এর সমান, কিন্তু N যখন 2147483647-এর কাছাকাছি, তখন i * i int overflow ঘটাতে পারে; n / i-তে সে ঝুঁকি নেই।

লুপের সীমা	N মৌলিক হলে সর্বোচ্চ ভাগ	সময় জটিলতা
2 থেকে N − 1	N − 2 বার	O(N)
2 থেকে N/2	প্রায় N/2 বার	O(N)
2 থেকে √N	প্রায় √N বার	O(√N)

পরীক্ষার টিপ: N < 2-কে আগে আলাদা করুন (১ মৌলিক নয়), √N পর্যন্ত ভাগ পরীক্ষা করুন এবং প্রথম উৎপাদক পেলেই break দিন।