কোন সংখ্যাকে দুইটি প্রাইম নাম্বারের যোগফল আকারে প্রকাশ।

কোন সংখ্যাকে দুইটি প্রাইম নাম্বারের যোগফল আকারে প্রকাশ।

N = p1 + p2;

আমরা সাধারনত দেখি প্রায় প্রতিটা কন্টেস্টেই একটা না একটা প্রবলেম নাম্বার থিওরি থেকে দেওয়া হয়। এর মধ্যে আমি আজ একটা প্রবলেম নিয়ে আলোচনা করব সেটা হচ্ছে।

**** কোন সংখ্যাকে দুইটি প্রাইম সংখ্যার যোগফল আকারে প্রকাশ করা???

যেমন সংখ্যাটি যদি ৩০ হয় তাহলে দুইটি প্রাইম সংখ্যার যোগফল আকারে প্রকাশ কর? আমরা বলতে পারি যে ৩০ = ১৩+১৭যেখানে ১৩১৭ প্রাইম সুতরাং আমাদের উত্তর টি সঠিক।এখন আমরা দেখি আসলে সব সংখ্যাকেই কি দুইটি প্রাইম সংখ্যার যোগফল আকারে প্রকাশ করা সম্ভব? যদি সম্ভব হয় তাহলে তা নির্নয় করি আর যদি না হয় তাহলে কোন ক্ষেত্রে সম্ভব নয় তা বের করি।

***প্রথমে আমরা বলে নেই সংখ্যাটি অবশ্যই এর থেকে বড় হতে হবে।

এখন আমরা দেখি সংখ্যাটি জোড় হয় তাহলে সলুশন আনা সম্ভব কিনা? যেহেতু আমরা জানি দুইটি বেজোড় সংখ্যার যোগফল সব সময় জোড় হয় । আর আমরা এও জানি যে পৃথীবিতে যত প্রাইম নাম্বার আছে তার সব সংখ্যায় বিজোড় শুধু দুই ব্যাতিত। সুতরাং আমরা জোড় সংখ্যার ক্ষেত্রে এমন একটি পেয়ার অবশ্যই পাব যার যোগফল আমদের সংখ্যাটির সমান হবে।

এই প্রগ্রাম টি দেখতে পার জোড় সংখ্যার ক্ষেত্রে ঘটনা সত্যি কিনা?

http://ideone.com/I0Vy4u
*** মুল বিষয়ঃ

এখন বিজোড় সংখ্যার ক্ষেত্রে আসা যাক। এই ক্ষেত্রে আমরা একটা চিন্তা মাথাই আনি ঐ চিন্তার মাধ্যমেই আমরা খুব সহজে বিজোড় সংখ্যার ক্ষেত্রে কখন ঘটনাটি সত্য হবে তা বের করে ফেলতে পারব। আর কখন ঘটনাটি মিথ্যা হবে তাও বের করতে পারব।

উপরে আমরা বলেছি যে কেবল দুই ব্যাতিত আর কোন সংখ্যা প্রাইম নেই যা জোড়।আর আমাদের সংখ্যাটি যদি বেজোড় হয় তাহলে দুইটি সংখ্যার যোগফল তখনি বেজোড় হবে যখন একটি সংখ্যা জোড় হবে। যেহেতু আমাদের কাছে কেবল মাত্র জোড় প্রাইম সংখ্যা একটি আছে সেহেতূ আমরা শুধু এত টুকুই চেক করলেই আমরা আমাদের উত্তর পেয়ে যাব তা হচ্ছে যদি ঐ বেজোড় সংখ্যাটি n হয় এবং n-2 যদি প্রাইম হয় তাহলেই কেবল আমরা বলতে পারব যে সংখ্যাটিকে দুইটি প্রাইম সংখ্যার যোগফল আকারে প্রকাশ করা সম্ভব তাছাড়া সম্ভব না সুতরাং আমাদের আর অন্য কোন সংখ্যা দিয়ে চেক করার প্রয়োজন হচ্ছেনা এতে আমদের সময় অনেক বেচে যাবে এবং আমরা TLE এর অভিশাপ থেকে মুক্তি পেতে পারব আশা করা যায়। যেমন ৪৩ = ২ + ৪১৪৫ = ২+৪৩ ৪৭ = ২+৪৫ false এখানে ৪৭ এর সময় আমাদের n-2 সংখ্যাটি প্রাইম নয় তাই আমরা বলতে পারি ৪৭ দুইটি সংখ্যার যোগফল আকারে প্রকাশ করা সম্ভব নয় কখনয় সম্ভব নয় বেপার টি না বুঝলে নিজে নিজে একটু ভাবেন তাহলেই পরিষ্কার হয়ে যাবে বিষয়টি।