ACM (UVa) : 10852


একটি integer n দেয়া আছে । এমন একটি প্রাইম সংখ্যা বের করতে হবে 
যেটি n থেকে ছোট বা সমান।

শর্তগুলো :
1. 100 <= n <= 10000
2. x <= n
3. n – p * x = maximum
4. p * x <= n < (p + 1) * x

৩ নাম্বার শর্তটি দেখি,
n – p * x = maximum হতে হবে।
আমাদেরকে ইনপুট হিসেবে n দেয়া থাকবে। 
এটা আমরা পরিবর্তন করতে পারি না
কাজেই, আমাদের চেষ্টা করতে হবে (p * x) যত ছোট করা যায়।
আলাদাভাবে, p যত ছোট করা যায় ততই ভাল এবং
x যত ছোট করা যায় ততই ভাল

এখানে বলা আছে p is an integer
তার মানে, ঋণাত্নক, , অঋণাত্নক যেকোন সংখ্যা হতে পারে। 

আচ্ছা ধরে নিই, p = -10
৪ নং শর্তটি কেমন দেখায়, 

-10x <= n < -9x

আমাদের অনেক ছোট একটা x নিতে হবে। সবচেয়ে ছোট x টি হলো 2
-20 <= n < -18
এটা কি সম্ভব ? প্রথম ভাগটুকু কিন্তু সম্ভব, -20 <= n
কিন্তু পরের ভাগটুকু হতে পারে না, n < -18

আমরা ১ নং শর্তটি দেখি,  100 <= n <= 10000
মানে, n এর মান একদম কম হলেও 100
-18'র জায়গায় কম করে হলেও 101 হতে হবে। n < 101

তার মানে p'র মান বাড়াতে হবে। ধরি,  p = -1 তাহলে ৪ নং শর্ত,
-x <= n < 0, এটিও অসম্ভব, কারন কম করে হলেও n < 101

p'র মান আরও বাড়াতে হবে। ধরি,  p = 0 তাহলে ৪ নং শর্ত,
0 <= n < x, এটিও অসম্ভব, কারন ২ নং শর্ত, x <= n
x ছোট বা সমান হতে পারে কিন্তু n'র চেয়ে বড় হতে পারে না।

p'র মান আরও বাড়াতে হবে। ধরি,  p = 1 তাহলে ৪ নং শর্ত,
x <= n < 2x, এটি সম্ভব !!
p সমান কম করে হলেও 1 হতেই হবে

তাহলে আমাদের শর্তগুলো দাড়াল,
1. 100 <= n <= 10000
2. x <= n
3. n – x = maximum
4. x <= n < 2x

৪ নং শর্তের ডানপাশের অংশটা দেখি।
n < 2x
এটিকে লেখা যায়, n / 2 < x
মানে, x কে কম করে হলেও n / 2 থেকে বড় হতে হবে।

সোজা কথায় আমাদের সম্পূর্ন প্রশ্নটি হল, 
n / 2 থেকে বড় প্রথম প্রাইম সংখ্যাটি বের করতে হবে !! :P

কি দরকার ছিল খামোখা এত জটিল করে এই সোজা কথাটা বলার ?
এখন কেউ ইচ্ছা করলে sieve ব্যবহার করতে পারে। 
তবে n কিন্তু বেশ ছোট, তাই আমি sieve ব্যবহার করিনি।
#include <iostream>
using namespace std;

int is_prime (int x) {
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0)
            return 0;
    }
    return 1;
}

int main ()
{
    int n, test;
    cin >> test;

    while (test--) {
        cin >> n;
        int k = n / 2 + 1;
        while (1) {
            if (is_prime (k)) {
                printf("%d\n", k);
                break;
            }
            k++;
        }
    }
    return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s