Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C#

C# में अभाज्य संख्या (Prime Number) जांचना

अभाज्य संख्या (Prime Number) वह पूर्णांक है जो 1 से बड़ा हो और जिसके केवल दो भाजक हों: 1 और स्वयं।

बुनियादी एल्गोरिदम (O(n))

int count = 0;
for (int i = 1; i <= n; i++) {
    if (n % i == 0) count++;
}
bool isPrime = (count == 2);

उदाहरण

using System;

namespace Demo {
    class MyApplication {
        public static void Main() {
            int n = 5, count = 0;

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

            if (count == 2) {
                Console.WriteLine("{0} is a Prime Number", n);
            } else {
                Console.WriteLine("Not a Prime Number");
            }
            Console.ReadLine();
        }
    }
}

आउटपुट

5 is a Prime Number

अनुकूलित एल्गोरिदम: O(√n)

यदि n का कोई भाजक है, तो उसका एक भाजक √n से कम या बराबर होना चाहिए।

public static bool IsPrime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;      // एकमात्र सम अभाज्य
    if (n % 2 == 0) return false; // अन्य सम संख्याएं

    for (int i = 3; i * i <= n; i += 2) { // केवल विषम संख्याएं जांचें
        if (n % i == 0) return false;
    }
    return true;
}

और अनुकूलन: 6k ± 1 पैटर्न

3 से बड़ी सभी अभाज्य संख्याएं 6k ± 1 रूप की होती हैं।

public static bool IsPrimeFast(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;      // 2, 3
    if (n % 2 == 0 || n % 3 == 0) return false;

    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

बड़ी संख्याओं के लिए: Miller-Rabin (संभाव्य)

// .NET में कोई बिल्ट-इन नहीं, लेकिन लाइब्रेरीज उपलब्ध हैं
// System.Numerics.BigInteger के लिए कस्टम कार्यान्वयन आवश्यक

प्रदर्शन तुलना (n = 10,000,019 के लिए)

एल्गोरिदम लगभग इटरेशन्स सापेक्ष गति
O(n) भाजक गिनती 10,000,019 1x (बेसलाइन)
O(√n) केवल विषम ~1,581 ~6,300x तेज
6k ± 1 ~527 ~19,000x तेज

मुख्य बिंदु

  • 1 अभाज्य नहीं है।
  • 2 एकमात्र सम अभाज्य संख्या है।
  • बड़े n के लिए हमेशा O(√n) या बेहतर एल्गोरिदम उपयोग करें।
  • क्रिप्टोग्राफी के लिए संभाव्य टेस्ट (Miller-Rabin) उपयोग किए जाते हैं।
  1. पायथन में जांचें कि कोई संख्या डाइहेड्रल अभाज्य संख्या है या नहीं पायथन में जांचें कि कोई संख्या डाइहेड्रल अभाज्य संख्या है या नहीं

    मान लीजिए हमारे पास एक संख्या n है। हमें जांचना है कि n डाइहेड्रल अभाज्य है या नहीं। एक संख्या डाइहेड्रल अभाज्य कहलाती है जब वह संख्या स्वयं अभाज्य हो और 7-सेगमेंट डिस्प्ले पर सामान्य या उल्टा (upside-down) दिखाने पर वही संख्या या कोई अन्य अभाज्य संख्या प्रदर्शित हो। उदाहरण के लिए, यदि इनपुट n = 11

  1. पायथन प्रोग्राम: अभाज्य संख्या जांचें पायथन प्रोग्राम: अभाज्य संख्या जांचें

    इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे। समस्या कथन हमें एक संख्या दी गई है, हमें जांचना है कि दी गई संख्या अभाज्य संख्या है या नहीं। 1 से बड़ी दी गई धनात्मक संख्या जिसके 1 और संख्या स्वयं के अलावा कोई अन्य गुणनखंड नहीं होते, उसे अभाज्य संख्या कहा जाता है। 2, 3, 5, 7 आदि अभाज्य संख्

  1. - Python प्रोग्राम: जांचें कि कोई संख्या अभाज्य है या नहीं

    इसमें, हम एक प्रोग्राम लिखेंगे जो जांच करेगा कि दी गई संख्या जो 1 से अधिक है, अभाज्य है या नहीं। एक अभाज्य संख्या 1 से बड़ा एक धनात्मक पूर्णांक है जिसके केवल दो गुणनखंड होते हैं 1 और वह संख्या स्वयं, उदाहरण के लिए संख्या: 2, 3, 5, 7... आदि अभाज्य संख्याएं हैं क्योंकि उनके केवल दो गुणनखंड होते हैं