Problem Description:
problem linkএক ব্যক্তি তার ইনকাম ট্যাক্স দিবেন । তার ইনকাম n টাকা ।
ট্যাক্স দেবার নিয়ম হলো - যদি x টাকার ট্যাক্স দেন, ট্যাক্স হবে x ছাড়া x এর সবচেয়ে বড় divisor ।
যেমন, তিনি যদি ৬ টাকার ট্যাক্স দেন, তবে তাকে ৩ টাকা ট্যাক্স দিতে হবে, যদি ২৫ টাকার ট্যাক্স দেন, তবে তাকে ৫ টাকা ট্যাক্স দিতে হবে ।
একইভাবে, x=35 হলে, Tax = 7 টাকা
লোকটি একটি বুদ্ধি বের করল, তিনি n টাকার ট্যাক্স একবারে দেবেন না, ভেঙ্গে ভেঙ্গে দেবেন । এমনভাবে দেবেন, যাতে তাকে সর্বনিম্ন Tax দিতে হয় । তবে তিনি ১ টাকার ট্যাক্স দিতে পারবেন না, যেহেতু ১ ছাড়া ১ এর আর কোন Divisor নেই ।
যেমন, তিনি ৩০ টাকার Tax দিতে চাইলে বিভিন্নভাবে দিতে পারেন-
৩০ = ২+২৮, Tax = ১+১৪ = ১৫টাকা
অথবা, ৩০ = ৩+২৭, Tax = ১+৯ = ১০ টাকা
অথবা, ৩০ = ৪+২৬, Tax = ২+১৩ = ১৫ টাকা
অথবা, ৩০ = ৫+২৫, Tax = ৫+৫ = ১০ টাকা
অথবা, ৩০ = ৬+২৪, Tax = ৩+১২ = ১৫ টাকা
অথবা, ৩০ = ৭+২৩, Tax = ১+১ = ২ টাকা
অথবা, ৩০ = ৮+১০+৭+৬, Tax = ৪+৫+১+৩ = ১৩ টাকা
...
...
...
অথবা, ৩০ = ৮+১০+৭+৬, Tax = ৪+৫+১+৩ = ১৩ টাকা
...
...
...
এভাবে, আরো অনেকভাবেই তিনি ট্যাক্স দিতে পারেন ।
মানে একটি সংখ্যাকে তিনি যত ভাবে বিভিন্ন সংখ্যার যোগফল হিসেবে প্রকাশ করতে পারেন, তত উপায়ে ট্যাক্স দিতে পারেন । তার মধ্য যেভাবে ট্যাক্স দিলে, সর্বনিম্ন ট্যাক্স দিতে হবে, তিনি সেইভাবে ট্যাক্স দেবেন ।
এক্ষেত্রে, n = ৩০ এর জন্য, যেহেতু ২ সর্বনিম্ন, তাই সর্বনিম্ন ২ টাকা ট্যাক্স দিবেন ।
তোমাকে বলতে হবে, n টাকার ট্যাক্স দিতে হলে, তিনি সর্বনিম্ন কত টাকা দিতে পারবেন ?
constraint: 2<=n<=2*10^9
অ্যানালাইসিস:
খেয়াল করে দেখ, Prime Number(মৌলিক সংখ্যা) ক্ষেত্রে ঐ সংখ্যা ছাড়া সবচেয়ে বড় Divisor হলো ১ ।
তাই যদি কোন সংখ্যাকে Prime Number এর যোগফল হিসেবে ভেঙ্গে প্রতিটি Prime Number এর জন্য আলাদা ভাবে ট্যাক্স দেন, তবে প্রতিটি Prime Number এর জন্য ১ টাকা করে ট্যাক্স দিতে হবে । সংখ্যাটিকে যত গুলি Prime Number এর যোগফল হিসেবে প্রকাশ করা হবে, মোট ট্যাক্স হবে তত ।
যেমন ৩০ এর জন্য ৩০ = ৭+২৩, এখানে ৭ ও ২৩Prime Number, তাই ট্যাক্স হবে ১+১ = ২ টাকা ।
এখন এইটা দেখার বিষয়, কোন সংখ্যাকে সর্বনিম্ন কতগুলি Prime Number এর যোগফল হিসেবে প্রকাশ করা যায় । এটিই এই সমস্যার সমাধান ।
তাহলে তুমি কিভাবে করবে?
তোমার মনে হতে পারে n পর্যন্ত Prime Number generate করে নিয়ে, দেখবে n কে সর্বনিম্ন কয়টি Prime Number এর যোগফল হিসেবে প্রকাশ করা যায় ।
কিন্তু এভবে করতে চাইলে, TLE খাবে ।
তাহলে এর চেয়ে সহজ উপায় কি? তুমি একটু চিন্তা করে দেখ তো ! আগে চিন্তা কর, না পারলে নিচের অংশ পড় ।
সমাধান:
কোন সংখ্যা যদি নিজেই Prime Number হয়, তবে তাকে আর ভাংতে হবে না । এক্ষেত্রে ট্যাক্স ১ টাকা ।
এখন খেয়াল কর, Goldbach's conjecture অনুযায়ী "Every even integer greater than 2 can be expressed as the sum of two primes"
তাহলে, যদি n=2 হয়, তবে যেহেতু n prime number, তাই ট্যাক্স হবে ১ টাকা । আর যদি অন্য কোন জোড় সংখ্যা হয়, তবে ট্যাক্স হবে ২ টাকা, যেহেতু বাকি সব জোড় সংখ্যাকেই দুইটি prime number এর যোগফল হিসেবে প্রকাশ করা যাবেই ।
তাহলে জোড় সংখ্যার জন্য সমাধান পেয়ে গেলাম ।
বিজোড় সংখ্যার জন্য সমাধান কি? একটু চিন্তা করে দেখ। না পারলে, নিচের অংশ দেখ ।
Goldbach's weak conjecture অনুযায়ী, "Every odd number greater than 5 can be expressed as the sum of three primes."
সমাধান তো পেয়ে গেলে !
এইটুকু পড়েই যদি সাবমিট করে থাক, তাহলে এতক্ষণে নিশ্চয় WA খেয়ে মাথা চুলকাচ্ছ !!
বিজোড় সংখ্যাকে ৩ টা প্রাইম নাম্বারের যোগফল হিসেবে প্রকাশ করা যায় ঠিকই, কিন্তু কখনো যদি দুইটি প্রাইম নাম্বারের যোগফল হিসেবে প্রকাশ করা যায়, তবে ?
যেমন, ১৫ কে ২+১৩ আকারে লেখা যায়। তাহলে ট্যাক্স হবে ২ টাকা ।
তাহলে কখন একটি বিজোড় সংখ্যাকে দুইটি প্রাইম নাম্বারের যোগফল হিসেবে প্রকাশ করা যাবে ?
২ ছাড়া অন্য দুইটি প্রাইম নাম্বারের যোগফল হিসেবে কখনোই প্রকাশ করা যাবে না । কারণ দুইটি বিজোড় সংখ্যার যোগফল কখনোই বিজোড় হবে না ।
তাই একটি ২ হতে হবেই । বাকি থাকল n-2 । এখন দেখতে হবে n-2 প্রাইম কিনা । যদি হয়, তাহলে সম্ভব ।
অর্থাৎ, যদি n বিজোড় হয় এবং n-2 প্রাইম হয়, তাহলেই কেবল মাত্র একটি বিজোড় সংখ্যাকে দুইটি প্রাইম নাম্বারের যোগফল হিসেবে প্রকাশ করা যাবে ।
এই হলো প্রোবলেমটির সমাধান !!