SPOJ AMR11E Solution

| July 01, 2015

The correct, optimal and working solution for programming question AMR11E on spoj

/*
 * AMR11E.cpp
 *
 *  Created on: Jun 9, 2014
 *      Author: Arpit Bhayani
 */

#include <string>
#include <cstdarg>
#include <utility>

#include <queue>
#include <stack>
#include <set>
#include <list>
#include <vector>
#include <queue>
#include <bitset>
#include <map>

#include <functional>
#include <sstream>
#include <algorithm>
#include <iostream>

#include <cstddef>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cstdio>

#include <stdexcept>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <cstdlib>
#include <cassert>
#include <ctime>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<double> VD;
typedef vector<VD> VVD;
typedef vector<string> VS;
typedef vector<VS> VVS;
typedef signed long long s64;
typedef unsigned long long u64;
typedef pair<int, int> PII;

#define all(a) a.begin(),a.end()
#define out(x) cout<<#x<<" = "<<(x)<<endl;
#define out2(x,y) out(x) out(y)
#define out3(x,y,z) out(x) out(y) out(z)
#define fillchar(a,i) memset(a,i,sizeof(a));
#define fori(i,max) for(int i=0;i<(int)(max) ;(i)++)
#define for2i(i,min,max) for(int i=min;i<(int)(max) ;(i)++)
#define forv(i,a) fori(i,(int)(a.size()))
#define forv2(i,j,a) forv(i,a) forv(j,(a)[i])
#define forIter(i, c) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)

const int MAX = 3000;
const int LMT = 1000;
const int LEN = 5000000;

int primes[1000000], number[1000000];

VI lucky;
void sieve() {
	for (int p = 2; p < MAX; p++) // for all elements in array
			{
		if (primes[p] == 0) { // it is not multiple of any other prime
			primes[p] = 1; // mark it as prime

			// mark all multiples of prime selected above as non primes
			int c = 2;
			int mul = p * c;
			for (; mul < MAX;) {
				primes[mul] -= 1;

				if (primes[mul] + 3 == 0) {
					//cout<<primes[mul]<<"\t"<<mul<<"\n";
					//getchar();
					lucky.push_back(mul);
				}
				c++;
				mul = p * c;
			}
		}
	}
	sort(lucky.begin(), lucky.end());
}

int main() {
	sieve();
	int t, n;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		printf("%d\n", lucky[n - 1]);
	}
	return 0;
}