vector <int> mas = {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161};

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define re return
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi (3.14159265358979323846264338327950288419716939937510)
#define fo(i, n) for(int i = 0; i < n; ++i)
#define ro(i, n) for(int i = n - 1; i >= 0; --i)
#define unique(v) v.resize(unique(all(v)) - v.begin())

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree;

vi v = {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161};

int main() {
    int n, x;
    cin >> n;
    fo(i, n) {
        cin >> x;
        cout << v[x - 1] << '\n';
    }
}

Should I use some test of simplicity (from Cormen or somewhere else) or is there any better way for such numbers?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Threading.Tasks;

namespace T1
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse (Console.ReadLine ());
            int[] data = new int[]{2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161};
            int[] result = new int[n];
            for (int i = 0; i < n; ++i)
                result [i] = data [int.Parse (Console.ReadLine ()) - 1];
            for (int i = 0; i < n; ++i)
                Console.WriteLine (result [i]);
        }
    }
}

The largest known prime number is currently the Mersenne prime 2^{57,885,161} - 1. Discovered January, 2013.

Edited by author 12.12.2013 01:30

this problem is easy

Edited by author 30.10.2013 13:06

http://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test - using this.

This code get 0.001
int main()
{
    int n, i, k,
        m[]={ 0, here must be numberz :) };  // 39 numbers
    scanf("%d",&k);
    for(i=0;i<k;i++)
    {
        scanf("%d",&n);
        printf("%d\n",m[n]);
    }
    return 0;
}

and this code get 0.015
int main()
{
    int n, i, k,
        m[]={here must be numberz :) };  // 38 numbers
    scanf("%d",&k);
    for(i=0;i<k;i++)
    {
        scanf("%d",&n);
        printf("%d\n",m[n-1]);
    }
    return 0;
}


Why 38 iterations of (n-1) so hardly influence for speed of execution ???

Edited by author 02.05.2007 01:47

Edited by author 18.02.2010 20:17

If the only method possible is cheating, what is the point in giving such problems. It doesnt test anything.

In the first string of condition: "For example, 2^2−1 — the first Mersenne prime".
So, the first Mersenne prime is 2^2-1 = 3.

Then, in the sample we read:
18   -   3217

But, if so, the first Mersenne prime is 2, not 3, so, for the test

1
1

the program should output 2, not 3.

2,3,5,7,13,17,19,31,61,89,107,127,521,607,                 1279,2203,2281,3217,4253,4423,9689,9941,                   11213,19937,21701,23209,44497,86243,
110503,132049,216091,756839,859433,
1257787,1398269,2976221,3021377,6972593,
13466917,20996011;

Is it all right? Cuz I got WA...
Help me.

Thanks for the author!!!

Edited by moderator 10.01.2007 00:32

oh no wa#1 noooooo
#include <mat.h>
#include <iostream.h>
int man(){
coout<<"NOOOOOOO";
}

Edited by author 14.04.2007 21:49

#include <iostream.h>
#include <math.h>
int prost(int a)
{
    int kol=0;
    for(int i=2;i<=int (sqrt(a));i++)
    {
        if(a%i==0)
            kol++;
    }
    if(kol==0)
        return 1;
    else
        return 0;
}
int main()
{
    int T,n,kol=0,i=0,p=2;
    cin>>T;
    for(int j=0;j<T;j++)
    {
        cin>>n;
        while(i!=n)
        {
            if((prost(pow(2,p)-1))==1)
            {
                i++;
            }
            if(i==n)
            {
                cout<<p<<' ';
            }
            p++;
        }

    }
    return 0;

}

Edited by author 28.03.2007 00:35

[code deleted]

Edited by moderator 28.07.2006 10:35

I' ve got 0, 001 second result.
This is an easy problem - impossible to solve without cheating but here yuo can find this useful list: http://primes.utm.edu/mersenne/index.html#known
;)