Blog

Problem link

আলোচনাঃ
Goldbach`s Conjecture, in this problem, আমাকে একটা number দেয়া থাকবে। Number টাকে যদি 2টা prime number এর যোগফল হিসেবে প্রকাশ করা যায়, তাহলে কতো উপায়ে ঐ number কে 2টা prime number এর যোগফল হিসেবে প্রকাশ করা possible তা বের করা লাগবে। যেমনঃ

আমরা জানি, 2,3,5,7,11,13,17,19,… এগুলো prime number.
তাহলে,

24-2=22; এখানে, 22 prime না।
24-3=21; এখানে, 21 prime না।
24-5=19; এখানে, 19 prime.তাহলে এটা একটা উপায়।
24-7=17; এখানে, 17 prime.তাহলে এটা একটা উপায়।

24-11=13; এখানে, 13 prime.তাহলে এটা একটা উপায়।

———————————————————————————————-

24-13=11; এখানে, 11 prime.তাহলে এটা একটা উপায়।

কিন্তু 13 আগেই হিসাব করেছি। কারণ, 11+13=24 আর 13+11=24 একই কথা।

তাহলে, 11 এর পরে আর কোনো prime number এর যোগফল হিসেবে 24 কে লেখা যায় কিনা
তা check করার দরকার নেই। কারণ , এর পরে already check করা prime number
গুলো repeat হচ্ছে।

Same Problem – UVA – 543 – Goldbach’s Conjecture

উত্তরঃ
তাহলে আমরা N থেকে prime number বিয়োগ করে সেই বিয়োগফলটা prime number কিনা check করব। যদি বিয়োগফলটাও prime number হয় তাহলে এটা একটা উপায়। তাই count++ করতে পারি। আচ্ছা বুঝলাম….কিন্তু কোন prime number পর্যন্ত check করবো?
উপরের আলোচনা অংশেই দেখিয়েছি যে, prime=13 নিলে সেটা repeat হয়। তাহলে ,
N/2 পর্যন্ত check করলেই হয়।

আর, বিয়োগফলটা prime কিনা সেটা বুঝবো কিভাবে? এটা বুঝার জন্য আমরা vis[] array
টার সাহায্য নিতে পারি। কারণ sieve() function এ আমরা একটা prime number এর
জন্য vis[prime]=0 আর non-prime এর জন্য vis[non-prime]=1 সেট করে রেখেছি।
তাহল, vis[n-prime[i]]; 0 নাকি 1 সেটা check করেই বুঝতে পারবো যে বিয়োগফলটা
prime নাকি non-prime.

বিঃদ্রঃ অনেক programmer sieve() implement করার সময় i=3 থেকে শুরু করে and
2nd loop এ j এর value update করার সময় j+=i+i লিখে। এভাবে sieve()
implement করার problem হচ্ছে যে, এখানে আমরা অনেক composite number কে
jump করে চলে যাই। এর কারণে ঐ composite number এর জন্য vis[x]=0 থেকে যায়।
কিন্তু composite number এর জন্য vis[x]=1 হওয়া দরকার। তাই এভাবে implement
করলে composite number এও vis[x]=0 দেখাবে কারণ bool vis[N] কে আমরা
global array হিসেবে declare করেছি। সুতরাং, তখন program আমাকে ভুল answer
দিবে। তাই এই problem এ আমরা i=3 and j+=i+i করবো না। না বুঝলে খাতা-কলমে
একটু test করলেই আশা করি ব্যাপারটা বুঝা যাবে।

C++ Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e7+10;
#define pii pair<int,int>
#define MOD 1000000007
#define PI acos(-1.0)
vector<ll> prime;
 
bool vis[N];
 
 
void sieve()
{
    for(ll i=2; i*i<=N; i++)
    {
        if(vis[i]==0)
        {
            for(ll j=i*i; j<=N; j+=i)
            {
                vis[j]=1;
            }
        }
    }
    for(ll i=2; i<=N; i++)
    {
        if(vis[i]==0) prime.push_back(i);
    }
 
}
 
 
int main()
{
    sieve();
 
    ll t,n,cs=1;
    cin>>t;
    while(t--){
        cin>>n;
        ll cnt=0;
        for(ll i=0;prime[i]<=(n/2);i++){
            /*
              check vis[n-prime[i]] is prime or not.
              if prime, than update cnt by plus one.
            */
            if(vis[n-prime[i]]==0) cnt++;
        }
        printf("Case %lld: %lld\n",cs++,cnt);
    }
 
}

Related Problem: UVA – 543 – Goldbach’s Conjecture, UVA – 10653 – Bombs! NO they are Mines!!