अभाज्य संख्या (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) उपयोग किए जाते हैं।