1805- Betrand-Chebyshev

Description

Zplinti1 has recently learn rand() function in C/C++. He is so excited, since he finds using that function is easy and convenient. For example, if you want to generate a integer randomly from 0 to 9, he can simply write “rand()%10”.

However, rand() function can’t generate a number which is too large. The maximum number is 32767, by default. Zplinti1 is not satisfied with that!

Clever as he is, he quickly gets a way: he can multiply some rand() functions together, to get a much larger number. If he write “( rand()%10000 ) * ( rand()%10000 )”, he can get a number as large as 9999*9999.

Unfortunately, one of his friends, bearchild, soon finds the problem: some numbers might not be got using his way described above. 
Zplinti1 wants to find the minimum number that cannot be got.

More precisely, we have n numbers, from a[0] to a[n-1]. And for number a[i], it is a value randomly chosen from 0 to b[i], 
then we set X as the product of those n numbers, what is the minimum 
positive number that cannot be the value of X? 
If there is no problem with the new function, output “Good Function”.

Input

The first line of input contains a number T, indicating the number of cases. (T <=1000)

For each case, the first line is a number n (1<= n <=10,000). 
The second line contains n numbers from b[0] to b[n-1], all those numbers are positive numbers less than 1,000,000,000.
Output

For each case, output “Case #i: “ first. (i is the number of the test case, from 1 to T). 
Then output the minimum value that X cannot be, or “Good Function”, as described above.

Sample Input

4
2
2 3
2
4 5
3
4 7 11
3
1 1 2
Sample Output

Case #1: 5
Case #2: 7
Case #3: 13
Case #4: Good Function
Hint

As you can see, the maximum number zplinti1 can get is the product of b[0] to b[n-1], when each rand() function get its largest number. If the answer you get is larger than this maximum, you have to output "Good Function", and it is the only case you need to output that.





#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

bool isPrime(long long n)
{
    if(n == 2) return true;
    if(n%2 == 0) return false;
    if(n == 3) return true;
    long long i = 3;
    for(i=3;i<(long long)pow(n,0.5);i+=2)
        if(n%i==0)
            return false;
    if(i>=n)
        return true;
    return true;
}

long long findFirstPrimeNumber(long long num)
{
    long long data = num;
    bool flag = false;
    while(!flag)
    {
        if(data%2 == 0)
            data++;
        else
            data += 2;
        flag = isPrime(data);
    }
    return data;
}

int main()
{
    int total = 0;
    cin >> total;
    vector<long long> data;
    vector<long long> result;
    result.resize(total);
    for(int i=0;i<total;i++)
    {
        int n = 0 ;
        cin >> n;
        data.resize(n);
        long long MaxNumber = 0;
        for(int j=0;j<n;j++)
        {
            cin >> data[j];
            if(j == 0)
                MaxNumber = data[j];
            else
            {
                if(MaxNumber < data[j])
                    MaxNumber = data[j];
            }
        }
        /*to find the first prime number that bigger than this*/
        long long test = 0;
        test = findFirstPrimeNumber(MaxNumber);
        if(test <= n)
            result[i] = 0;
        else
            result[i] = test;
    }

    for(int k=0;k<(int)result.size();k++)
    {
        if(result[k] <= 0)
            cout << "Case #" << k+1 <<":" << "Good Function" << endl;
        else
            cout << "Case #" << k+1 <<":" << result[k] << endl;
    }
    return 0;
}