C भाषा मा अभाज्य संख्या निर्धारणको पूर्ण व्याख्या! परीक्षण विभाजन·एराटोस्थेनेस छान्ने·अनुकूलन

1. परिचय

C भाषा सिक्ने प्रक्रियामा, 「प्राइम नम्बर जाँच」 अक्सर देखिने आधारभूत समस्याहरू मध्ये एक हो। प्रोग्रामिङ शुरुआतीहरूका लागि, 「संख्याको गुणधर्म बुझ्ने, उपयुक्त एल्गोरिदम चयन गर्ने क्षमता」 हासिल गर्ने राम्रो अवसर हो। त्यसै गरी, अझ प्रभावकारी प्राइम नम्बर जाँच एल्गोरिदम सिकेर, एल्गोरिदमको गणनात्मक जटिलता र प्रोग्रामको अनुकूलनबारे पनि बुझाइ गहिरो हुन्छ।

यस लेखमा, C भाषा प्रयोग गरेर प्राइम नम्बर जाँच गर्ने विधि प्रस्तुत गरिन्छ, र वास्तविक रूपमा चल्ने नमुना कोड प्रदान गरिन्छ। मूलभूत ट्रायल डिभिजन विधिबाट, अझ तेज Eratosutenesu को छान्ने (फुरुई) सम्म, विभिन्न विधिहरूलाई समेटिन्छ।

2. अभाज्य संख्या के हो?

अभाज्य संख्या भन्नाले, 1 र त्यो संख्याको आफैँ बाहेक सकारात्मक भाजक नहुनु भएको प्राकृतिक संख्या हो। उदाहरणका लागि, 2, 3, 5, 7, 11 आदि अभाज्य संख्याहरू हुन्।

2.1. अभाज्य संख्याका मूलभूत विशेषताहरू

• सबैभन्दा सानो अभाज्य संख्या 2 हो（एकमात्र सम अभाज्य संख्या）
• 1 अभाज्य संख्या होइन（भाजक केवल 1 मात्र भएको कारण）
• अभाज्य संख्याहरू अनन्त रूपमा अवस्थित छन्
• यदि 2 वा सोभन्दा ठूलो पूर्णांक n अभाज्य छैन भने, यो निश्चित रूपमा 2 वा सोभन्दा ठूलो अभाज्य संख्याले विभाजित हुन्छ

2.2. अभाज्य संख्याका विशिष्ट उदाहरणहरू

3. C भाषा मा आधारभूत अभाज्य संख्या निर्धारण विधि（🔰 शुरुआतीहरूका लागि）

यहाँ, सबैभन्दा आधारभूत विधि हो「परीक्षण विभाजन विधि」लाई परिचय गराइन्छ।

3.1. परीक्षण विभाजन विधि（आधारभूत）

परीक्षण विभाजन विधि भनेको, 2 भन्दा ठूलो वा बराबरको पूर्णांक N का लागि, 1 र N आफैँ बाहेकका पूर्णांकहरूले भाग जानेछ कि छैन जाँच गर्ने विधि हो।

• यदि N 2 भन्दा ठूलो वा बराबरको पूर्णांक हो भने, 2 देखि N-1 सम्मको संख्याले भाग जानेछ कि जाँच गर्नुहोस्
• यदि भाग जाने संख्या भेटिएमा「संयोजन संख्या」、नभए「अभाज्य संख्या」

नमूना कोड（आधारभूत संस्करण）

#include <stdio.h>

int is_prime(int n) {
    if (n < 2) return 0;  // 1 भन्दा कम वा बराबरको संख्या प्राइम होइन
    for (int i = 2; i < n; i++) {  // 2 देखि n-1 सम्म विभाज्य छ कि छैन जाँच गर्नुहोस्
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int num = 7;
    if (is_prime(num))
        printf("%d प्राइम संख्या होn", num);
    else
        printf("%d प्राइम संख्या होइनn", num);
    return 0;
}

चलाउने परिणाम

7 एक अभाज्य संख्या हो।

यो विधि सरल र बुझ्न सजिलो छ, तर गणना जटिलता O(N) ठूलो भएको कारण, N ठूलो भएमा प्रक्रिया समय लामो हुन्छ भन्ने कमी छ। अर्को भागमा, अझ प्रभावकारी विधि परिचय गराइन्छ।

4. C भाषा मा प्रभावकारी रूपमा प्राइम संख्या निर्धारण गर्ने विधि【Eratosthenes को छनौनी・परीक्षण विभाजन विधि सुधार संस्करण】

प्राइम संख्या निर्धारणको गणना अनुकूलन गर्नका लागि, तलका दुईवटा विधिहरूलाई व्याख्या गर्नेछौं।

1. √N सम्मको परीक्षण विभाजन विधि（सुधार）
2. Eratosthenes को छनौनी（छनौनी）

4.1. √N सम्मको परीक्षण विभाजन विधि（सुधार）

प्राइम नहुनु भएको संख्या N मा, अनिवार्य रूपमा √N भन्दा तलको भाजक अवस्थित हुन्छ, त्यसैले N को वर्गमूलसम्मको दायरा मात्र जाँच गर्नुपर्छ भन्ने नै मुख्य बुँदा हो।

नमूना कोड

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

int is_prime_optimized(int n) {
    if (n < 2) return 0;
    if (n % 2 == 0 && n != 2) return 0;  // २ बाहेकको सम संख्या मूल संख्या होइन
    for (int i = 3; i <= sqrt(n); i += 2) {  // केवल विषम संख्याहरू जाँच्नुहोस् (सम संख्याहरू छोड्नुहोस्)
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int num = 29;
    if (is_prime_optimized(num))
        printf("%d एक मूल संख्या होn", num);
    else
        printf("%d एक मूल संख्या होइनn", num);
    return 0;
}

चलाउने परिणाम

29 एक अभाज्य संख्या हो।

यो विधिद्वारा, गणनात्मक जटिलता O(N) → O(√N) मा सुधार हुन्छ, ठूलो संख्याहरूको लागि पनि छिटो निर्धारण गर्न सकिन्छ।

4.2. Eratosthenes को छनौनी（छनौनी）

Eratosthenes को छनौनी भनेको, “साना प्राइम संख्याहरूको गुणकहरूलाई हटाएर, प्राइम संख्याहरूलाई प्रभावकारी रूपमा पत्ता लगाउने एल्गोरिदम” हो।

• 2 बाट सुरु गरेर, त्यसका सबै गुणकहरूलाई हटाउने
• अर्को चरणमा बाँकी सबैभन्दा सानो संख्या（3）को गुणकहरूलाई हटाउने
• यसलाई दोहोर्याउँदा मात्र प्राइम संख्याहरू बाँकी रहन्छ

नमूना कोड

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

void sieve(int n) {
    bool prime[n + 1];
    for (int i = 0; i <= n; i++) prime[i] = true;

    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }

    for (int p = 2; p <= n; p++)
        if (prime[p])
            printf("%d ", p);
    printf("n");
}

int main() {
    int n = 50;
    sieve(n);
    return 0;
}

चलाउने परिणाम

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Eratosthenes को छनौनीको गणनात्मक जटिलता O(N log log N) हो, धेरै प्राइम संख्याहरू खोज्नुपर्ने अवस्थामा उत्तम हो।

5. C言語 को अभाज्य संख्या निर्धारण एल्गोरिदमको प्रदर्शन तुलना【गति मापन र अनुकूलन】

अभाज्य संख्या निर्धारण एल्गोरिदममा केही विभिन्न विधिहरू छन्, तर प्रत्येककोप्रोसेस गति र कार्यक्षमता धेरै फरक हुन्छ। यस खण्डमा, तलका 3 विधिहरूको बारेमा, C言語 मा कार्यसमय मापन गरी, कुन विधि कुन परिस्थितिमा प्रभावकारी छ भन्ने विचार गरिन्छ।

• परीक्षण विभाजन विधि（मूल）: O(N)
• √N सम्मको परीक्षण विभाजन विधि（अनुकूलन）: O(√N)
• Eratosutenesu को छन्नी（दायरा भित्रको अभाज्य संख्या खोज्दा）: O(N log log N)

5.1. कार्यसमय मापन विधि

C言語 मा, प्रोसेस समय मापन गर्न, clock() फलन प्रयोग गर्न सकिन्छ।

मूलभूत कार्यसमय मापनको नमुना कोड

#include <stdio.h>
#include <time.h>

void measure_time(void (*func)(int), int n) {
    clock_t start, end;
    start = clock();  // मापन सुरु

    func(n);  // मापन गरिने फङ्सन चलाउनुहोस्

    end = clock();  // मापन समाप्त
    printf("Execution time: %lf secondsn", (double)(end - start) / CLOCKS_PER_SEC);
}

5.2. प्रत्येक विधिको कार्यसमय मापन

5.2.1. परीक्षण विभाजन विधि（O(N））

कोड

int is_prime(int n) {
    if (n < 2) return 0;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

void test_trial_division(int limit) {
    int count = 0;
    for (int i = 2; i <= limit; i++) {
        if (is_prime(i)) count++;
    }
    printf("Total primes: %dn", count);
}

5.3. कार्यसमयको तुलना（ग्राफिकरण）

Eratosutenesu को छन्नी अत्यन्त तेज छ भन्ने कुरा स्पष्ट हुन्छ।

6. FAQ（सामान्य प्रश्नहरू）

यस खण्डमा, C भाषा मा अभाज्य संख्या निर्धारण सम्बन्धी प्राय सोधिने प्रश्नहरूका उत्तर दिनेछौं।

Q1: किन अभाज्य संख्या निर्धारणमा वर्गमूल प्रयोग गरिन्छ?

A:
यदि कुनै संख्या N अभाज्य छैन भने, सधैँ N को वर्गमूल भन्दा तल भाजकहरू अवस्थित हुन्छन् भन्ने गणितीय गुण हुन्छ।

उदाहरणका लागि, N = 49 को अवस्थामा, भाजकको जोडीहरू तल देखाइएका छन्।

• 1 × 49
• 7 × 7（वर्गमूल）
• 49 × 1

वर्गमूल भन्दा माथिका भाजकहरू पहिले नै चरणमा जाँच गरिसकेका छन्, त्यसैले गणनात्मक जटिलता O(N) बाट O(√N) मा घटाउन सकिन्छ।

Q2: Eratosthenes को छन्नी कुन परिस्थितिमा प्रयोग गर्नु पर्छ?

A:
Eratosthenes को छन्नी, कुनै दायरा भित्रका सबै अभाज्य संख्याहरूलाई छिटो पत्ता लगाउन चाहनुहुन्छ भने मा उपयुक्त छ।

✅ Eratosthenes को छन्नी प्रयोग गर्ने केसहरू

• 1 देखि 100万 सम्मको अभाज्य संख्याहरूलाई सूचीबद्ध गर्न चाहन्छु
• धेरै संख्याहरूको अभाज्य निर्धारणलाई प्रभावकारी रूपमा गर्न चाहन्छु

Q3: C भाषा को वातावरण अनुसार अभाज्य निर्धारणको गति परिवर्तन हुन्छ?

A:
हो, C भाषा को कम्पाइलर, अनुकूलन विकल्प, कार्यान्वयन वातावरण द्वारा अभाज्य निर्धारणको गति धेरै परिवर्तन हुन्छ।

✅ प्रभाव पार्ने तत्वहरू

• कम्पाइलरको प्रकार（GCC, Clang, MSVC जस्ता）
• कम्पाइल गर्दा अनुकूलन विकल्प
• CPU को प्रदर्शन（विशेष गरी लूप प्रक्रिया गति मा प्रभाव）

💡 गति बृद्धि सुझाव

gcc -O3 prime.c -o prime

यसले कम्पाइलरलाई लूपको अनुकूलन गर्न मद्दत गर्छ, जसले प्रक्रिया छिटो बन्ने सम्भावना हुन्छ।

7. सारांश र भविष्यको अध्ययनको दिशा

अहिलेसम्मको सेक्सनमा, C भाषा प्रयोग गरेर प्राइम नम्बर निर्धारणको मूलभूतदेखि अनुप्रयोगसम्मलाई विस्तृत रूपमा व्याख्या गरेका छौं।

7.1. लेखको समग्र सारांश

🔹 प्राइम नम्बर भनेको के हो?

• 1 र त्यो संख्यै बाहेक कुनै भाजक नहुनु हुने प्राकृतिक संख्या
• यदि वर्गमूलसम्म जाँच गरेमा, अनावश्यक गणना घटाउन सकिन्छ（गणना जटिलता O(√N)）

🔹 C भाषा मा प्राइम नम्बर निर्धारण विधि

🔹 उपयुक्त एल्गोरिदमको चयन

7.2. भविष्यको अध्ययन दिशा

1️⃣ अधिक उन्नत प्राइम निर्धारण एल्गोरिदम

• Miller-Rabin प्राइम निर्धारण विधि（संभाव्य）
• AKS प्राइम निर्धारण विधि（निर्णायक）

2️⃣ C भाषा मा अनुकूलन प्रविधि

• कम्पाइलरको अनुकूलन विकल्प（-O2、-O3）
• मल्टिथ्रेड प्रयोग गरेर समानान्तर प्रक्रिया

3️⃣ C भाषा मा ठूलो संख्याको ह्यान्डलिंग

7.3. व्यावहारिक परियोजना प्रस्ताव

✅ परियोजना 1: प्राइम काउन्टर
✅ परियोजना 2: प्राइम फ्याक्टराइजेशन टूल
✅ परियोजना 3: प्राइम खोज एप

7.4. सारांश

• • ट्रायल डिभिजन विधि（मूलभूत）को गणना जटिलता O(N) भएको कारण सुस्त छ, त्यसैले ठूलो संख्याका लागि उपयुक्त छैन।
  • √N ट्रायल डिभिजन विधिको गणना जटिलता O(√N) हो, र ठूलो संख्याको एकल निर्धारणमा उपयुक्त छ।
  • एराटोस्थेनेसको चलनीको गणना जटिलता O(N log log N) हो, र छिटो प्राइम सूची प्राप्त गर्न सकिन्छ।
  • उपयोग अनुसार उपयुक्त एल्गोरिदम चयन गर्नु महत्त्वपूर्ण!