UVa 897 - Anagrammatic Primes

Problem Statement : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=838

Hints : 

1. There is no Anagrammatic Prime in the interval [991,10000000]. So for any number N >= 991, it would be efficient to print 0. Therefore, checking prime upto 1000 is enough for this problem.

2. If any from the rest of primes have any even digit, it can't be an Anagrammatic Prime.

3. Now, just iterate the prime[] array upto 999 and check their digits and all the permutations also. If any of the permutation is not prime, the ith number can't be an Anagrammatic Prime.

4. Permutation can be generated by backtracking, but you can implement next_permutation from C++ STL. 😊

5. After checking all the Anagrammatic Primes, just store them in an array (I used std::vector).

6. Now, make l, the next power of 10 greater than n and run a loop from n+1 to l. Compare them with the stored Anagrammatic Primes. If found, print that. Otherwise, print 0.

Solution : Here is my solution uploaded on GitHub. Before seeing the solution ensure that you have tried enough. 😃

UVa-Solutions/897 - Anagrammatic Primes.cpp

Discussion

• UVa 10791 - Minimum Sum LCM
• UVa 897 - Anagrammatic Primes

UVa 10791 - Minimum Sum LCM

প্রবলেম লিঙ্ক : https://goo.gl/9xPtfS

তোমাকে একটি সংখ্যা N দেওয়া থাকবে। কমপক্ষে এমন দুইটি সংখ্যার যোগফল বের করতে হবে যাদের ল.সা.গু হবে N এবং যোগফলটি হবে সর্বনিম্ন। ল.সা.গু বের করার একটি পদ্ধতি হতে পারে Prime Factorization. আমরা এখানে N-এর Prime Factorization করতে পারি। প্রতিটি প্রাইমের জন্য তাদের সর্বোচ্চ পাওয়ারের যোগফলই হবে আমাদের কাঙ্ক্ষিত আউটপুট। কিন্তু আমাদের আবার ক্রিটিকাল কেইস নিয়েও ভাবতে হবে। যদি N-এর মান 1 হয়, কিংবা N একটি প্রাইম হয় কিংবা N-এর মাত্র একটিই প্রাইম ফ্যাক্টর থাকে, তবে আউটপুট হবে N+1.

আমরা এবার কিছু উদাহরণ দেখি। 😀

N যখন 1 : 1 = 1 * 1; এক্ষেত্রে আমরা 1+1 = 2-ই পাবো। কারণ, এই এক জোড়া 1 বাদে 1-এর আর কোন একাধিক সংখ্যার ল.সা.গু হওয়া সম্ভব না।

N যখন প্রাইম : 2 = 1 * 2, 3 = 1 * 3, 5 = 1 * 5; এক্ষেত্রেও আমরা N+1-ই পাবো। কারণ, 1 আর N বাদে N-এর আর কোন একাধিক সংখ্যার ল.সা.গু হওয়া সম্ভব না।

N-এর প্রাইম ফ্যাক্টর যখন মাত্র একটিই : 4 = 2 * 2, 27 = 3 * 3 * 3, 64 = 2 * 2 * 2 * 2 * 2 * 2, 81 = 3 * 3 * 3 * 3; এসব ক্ষেত্রেও N-এর 1 আর N বাদে N-এর আর কোন একাধিক সংখ্যার ল.সা.গু হওয়া সম্ভব না। কারণ, এক্ষেত্রে প্রাইমই আছে একটি। আমরা যদি ওই প্রাইমটির সর্বোচ্চ পাওয়ার বের করি তবে সেটা শেষমেশ N-ই হবে। 😛 কিন্তু আমার তো শুধু N দিয়েই কাজ হচ্ছে না, কারণ মিনিমাম দুইটা সংখ্যা লাগবে।  আমরা জানি, 1 আর N-এর ল.সা.গু সবসময়ই N. তাই আমরা এখানেও চোখ বন্ধ করে বলে দিতে পারি, আউটপুট হবে N+1.

যখন N একটি নিরীহ শান্তশিষ্ট সংখ্যা  : আমরা এইসব কেইসের জন্য N-এর Prime Factorization করব। তারপর N-এর প্রাইম ফ্যাক্টরগুলোর পাওয়ার নিয়ে যোগ করতে থাকব এবং যোগফলটাই হলো আউটপুট। এখানে সর্বোচ্চ পাওয়ারের কথা কেন বলা হলো এবার আমরা নিচের উদাহরণের মাধ্যমে দেখি। 😊

ধরা যাক, আমাকে 4, 6 আর 12-এর ল.সা.গু বের করতে হবে। আমরা প্রতিটাকে Prime Factorize করি। 

4 = 2^2

6 = 2 * 3

12 = 2^2 * 3

দেখা যাচ্ছে, এখানে প্রাইম ফ্যাক্টরগুলো হলো, 2 আর 3; 2-এর সর্বোচ্চ পাওয়ার হলো 2 আর 3-এর সর্বোচ্চ পাওয়ার হলো 1. তাহলে আমরা ল.সা.গু পাই, 2^2 * 3^1 = 12 আর পাওয়ারগুলো যোগ করে পাই, 2^2 + 3 = 7.

এখন 7-ই যে আমাদের সর্বনিম্ন যোগফল তা বুঝতে আমরা আরেকটু সামনে এগোই।

12 এর ফ্যাক্টরগুলো হচ্ছে -> 1, 2, 3, 4, 6, 12.
আবার, 12 = 1 * 12 = 2 * 6 = 3 * 4.

সর্বনিম্ন যোগফলের জন্য আমার এখানে দুইটা সংখ্যা  নিলেই হচ্ছে। এর বেশি নিলে সর্বনিম্ন যোগফল পাওয়া যাবে না।
দুইটি সংখ্যার জন্য, আমরা পাই, 12 = 1 * 12 = 3 * 4
এখানে, 1+12 > 4+3  
বা, 13 > 7.
সুতরাং, 12 এর জন্য আউটপুট হবে 7. 😊

এই ছিল UVa 10791 - Minimum Sum LCM এর সল্যুশন হিন্ট। বুঝতে সমস্যা হলে কমেন্ট করতে ভুল করো না। 😊