অয়লার প্রাইম থেওরেম প্রবলেম

গোলবাচের ধারনা বা কঞ্জেকচার এবং অয়লারের থেওরেম।

গোলবাচের ধারনা বা গোলবাচের কঞ্জেকচার অনুযায়ী "২ এর চেয়ে বড় যে কোন সংখ্যাকে ৩ টা প্রাইম নাম্বারের যোগফল আকারে প্রকাশ করা যায় " তিনি ১ কে প্রাইম বা মৌলিক সংখ্যা হিসেবে চিন্তা করেছেন ।বিশ্বাস না হলে কাগজ কলম নিয়া একটু গুতা-গুতি করলেই বুঝতে পারবেন। আর আপনি চাইলে এই কঞ্জেকচারটাকে প্রমান করার চেষ্টাও করতে পারেন। যদি সফল হন তবে আপনাকে আর পায় কে? বিখ্যাত গনিতবিদ অয়লার এই কঞ্জেকচারকে আরও একটু বৃদ্ধি করে নতুন থেওরেম প্রমান করেন যা হল "৪ এর চেয়ে বড় বা সমান যে কোন জোড় সংখ্যাকে দুটি প্রাইম নাম্বারের যোগফল আকারে প্রকাশ করা যায়"। পরবর্তিতে তিনি নতুন থেওরেম প্রমান করেন যা হল "৭ এর চেয়ে বড় যে কোন সংখ্যা (জোড় বা বিজোড়) কে ৪ টা প্রাইম বা মৌলিক সংখ্যার যোগফল আকারে প্রকাশ করা যায়"।

উপরোক্ত তত্ত্বের ভিত্তিতে UVa 10168 প্রবলেমটা সেট করা হয়েছে। একবার ঠুস মেরে দেখতে পারেন। প্রবলেমটিতে ইনপুট সংখ্যাটি সর্বচ্চ্য 10^7 হতে পারে। সুতরাং সাধারণ ভাবে প্রাইম বের করার এখানে টেকনিক কাজ করবে না। এ জন্য আপনাকে সিভ মেথড শিখতে হবে। বাকি কাজটা একটু মাথা ঘামালেই পারবেন বলে আশা করি।

Problem Link: 10168 - Summation of Four Primes

N:B: Please don't copy the source code because it damages your brain.Try yourself first.Try to figure out the bug and critical test case.

Source Code in C++.

#include<bits/stdc++.h>
#define file freopen("in.txt","rt",stdin)
using namespace std;
int mark[10000009],prime[1000000],nprime =1;
int limit,n;
void PrimeNumber() /** Seive Method **/
{
    mark[1]=1;
    mark[0] =1;
    prime[nprime++]=2;

    for(int i=4; i<=n; i+=2)
        mark[i]=1;

    for(int i=3; i<=n; i+=2)
    {
        if(!mark[i])
        {
            prime[nprime++]=i;

            if(i<=limit)
            {
                for(int j=i*i; j<=n; j=j+i*2)
                {
                    mark[j]=1;
                }
            }
        }
    }

}
int main()
{
    //file;
    n = 10000009;
    limit = sqrt(n+1);
    PrimeNumber();
    int n,d1,d2,x,y,z,w;
    while(scanf("%d",&n)==1)
    {
        if(n<=7)
        {
            printf("Impossible.\n");
            continue;
        }
        if(n%2==1)
        {
            d2 = n - 5;
            x = 2;
            y = 3;
            for(int i=1; prime[i]<=d2; i++)
            {
                int diff = d2 - prime[i];
                if(mark[diff]==0)
                {
                    z = prime[i];
                    w = diff;
                    break;
                }
            }
            printf("%d %d %d %d\n",x,y,z,w);
        }
        else
        {

            d1 = n/2;
            if(d1%2==1)
            {
                int k = n-4;
                x = 2;
                y =2;
                for(int i=1; prime[i]<=k; i++)
                {
                    int diff = k - prime[i];
                    if(mark[diff]==0)
                    {
                        z = prime[i];
                        w = diff;
                        break;
                    }
                }
                printf("%d %d %d %d\n",x,y,z,w);
            }
            else
            {
                for(int i=1; prime[i]<=d1; i++)
                {
                    int diff = d1 - prime[i];
                    if(mark[diff]==0)
                    {
                        printf("%d %d %d %d\n",prime[i],diff,prime[i],diff);
                        break;
                    }
                }
            }
        }
    }
    return 0;
}