জাভা প্রোগ্রাম: একটি সংখ্যা দুটি প্রাইমের যোগফল হিসেবে প্রকাশ করা যায় কিনা চেক করা

গোলডব্যাকের অনুমান (Goldbach's Conjecture)

১৭৪২ সালে ক্রিস্টিয়ান গোলডব্যাক অনুমান করেছিলেন যে, **২-এর চেয়ে বড় প্রতিটি জোড় সংখ্যা দুটি প্রাইম নাম্বারের যোগফল হিসেবে প্রকাশ করা যায়**। এটি এখনও প্রমাণিত হয়নি কিন্তু ৪×১০¹⁸ পর্যন্ত যাচাই করা হয়েছে।

উদাহরণ:

• ৪ = ২ + ২
• ১০ = ৩ + ৭ = ৫ + ৫
• ৪৩ = ২ + ৪১ (বিজোড় সংখ্যার জন্য শুধু ২ + (n-2) চেক করলেই হয়)

ইনপুট ও আউটপুট উদাহরণ

ইনপুট:

Enter the number : 43

আউটপুট:

The number can be expressed as sum of two prime numbers.
The possible solutions are :
43 = 2 + 41

অ্যালগরিদম

1. প্রোগ্রাম শুরু করুন
2. দুটি ইন্টিজার ভেরিয়েবল ঘোষণা করুন: my_input, i
3. ব্যবহারকারী থেকে সংখ্যা ইনপুট নিন
4. IsPrime(num) হেল্পার ফাংশন ডিফাইন করুন
5. ফর লুপ চালান i = 2 থেকে my_input/2 পর্যন্ত
6. যদি i এবং (my_input - i) উভয় প্রাইম হয়, তবে প্রিন্ট করুন
7. যদি কোনো পেয়ার না পাওয়া যায়, "cannot be expressed" প্রিন্ট করুন
8. প্রোগ্রাম শেষ করুন

উদাহরণ ১: ব্যবহারকারী ইনপুট নেওয়া

import java.util.Scanner;

public class SumOfPrimes {
    public static void main(String[] args) {
        int my_input, i;
        boolean my_temp = false;
        my_input = 43;
        
        System.out.println("Required packages have been imported");
        Scanner my_scanner = new Scanner(System.in);
        System.out.println("A reader object has been defined");
        System.out.print("Enter the number : ");
        my_input = my_scanner.nextInt();
        
        for (i = 2; i <= my_input / 2; ++i) {
            if (IsPrime(i)) {
                if (IsPrime(my_input - i)) {
                    System.out.println("The number can be expressed as sum of two prime numbers.");
                    System.out.println("The possible solutions are :");
                    System.out.printf("%d = %d + %d\n", my_input, i, my_input - i);
                    my_temp = true;
                }
            }
        }
        
        if (!my_temp)
            System.out.println(my_input + " cannot be expressed as the sum of two prime numbers.");
    }
    
    static boolean IsPrime(int num) {
        boolean my_prime = true;
        for (int i = 2; i <= num / 2; ++i) {
            if (num % i == 0) {
                my_prime = false;
                break;
            }
        }
        return my_prime;
    }
}

উদাহরণ ২: পূর্বনির্ধারিত মান ব্যবহার

public class SumOfPrimes {
    public static void main(String[] args) {
        int my_input = 43, i;
        boolean my_temp = false;
        System.out.println("The number is defined as " + my_input);
        
        for (i = 2; i <= my_input / 2; ++i) {
            if (IsPrime(i)) {
                if (IsPrime(my_input - i)) {
                    System.out.println("The number can be expressed as sum of two prime numbers.");
                    System.out.println("The possible solutions are :");
                    System.out.printf("%d = %d + %d\n", my_input, i, my_input - i);
                    my_temp = true;
                }
            }
        }
        
        if (!my_temp)
            System.out.println(my_input + " cannot be expressed as the sum of two prime numbers.");
    }
    
    static boolean IsPrime(int num) {
        boolean my_prime = true;
        for (int i = 2; i <= num / 2; ++i) {
            if (num % i == 0) {
                my_prime = false;
                break;
            }
        }
        return my_prime;
    }
}

কোড ব্যাখ্যা

• লুপ লিমিট (i <= n/2): дуপ্লিকেট পেয়ার এড়াতে (2+41 এবং 41+2 একই)
• IsPrime ফাংশন: O(n/2) কমপ্লেক্সিটি, sqrt(n) দিয়ে অপ্টিমাইজ করা যায়
• বিজোড় সংখ্যা হ্যান্ডলিং: বিজোড় = প্রাইম + প্রাইম হলে একটু প্রাইম ২ হতে হবে (একমাত্র জোড় প্রাইম)

অপ্টিমাইজড IsPrime (O(√n))

static boolean isPrimeOptimized(int num) {
    if (num <= 1) return false;
    if (num <= 3) return true;        // 2, 3 are prime
    if (num % 2 == 0 || num % 3 == 0) return false; // 2, 3 দিয়ে বিভাজ্য
    
    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0)
            return false;
    }
    return true;
}

সিভ অফ এরাটোस्थেনিস (Sieve of Eratosthenes) - বহু কোয়েরি হলে

যদি একাধিক সংখ্যা চেক করতে হয় বা বড় রেঞ্জের প্রাইম লাগে:

public static boolean[] sieve(int limit) {
    boolean[] isPrime = new boolean[limit + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i <= limit; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= limit; j += i)
                isPrime[j] = false;
        }
    }
    return isPrime;
}

// ব্যবহার
boolean[] primes = sieve(1000000);
for (int i = 2; i <= n/2; i++) {
    if (primes[i] && primes[n - i]) {
        System.out.println(n + " = " + i + " + " + (n - i));
    }
}

বিজোড় সংখ্যা স্পেশাল কেস

public static void checkOdd(int n) {
    if (n <= 2) { System.out.println("Not possible"); return; }
    if (isPrime(n - 2))
        System.out.println(n + " = 2 + " + (n - 2));
    else
        System.out.println("Cannot be expressed");
}

তুলনা

বাস্তব প্রয়োগ

• ক্রিপ্টোগ্রাফি (RSA কি জেনারেশনে প্রাইম পেয়ার)
• নম্বর থিওরি রিসার্চ
• কম্পিটিটিভ প্রোগ্রামিং
• গোলডব্যাক পার্টিশান গণনা