verify/spoj/spoj-TDKPRIME.test.cpp

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Problem: https://www.spoj.com/problems/TDKPRIME/

Depends on

• Linear Sieve (library/number-theory/linear-sieve.hpp)

Code

#define PROBLEM "https://www.spoj.com/problems/TDKPRIME/"

#include <bits/stdc++.h>

using namespace std;

#include "../../library/number-theory/linear-sieve.hpp"

const int N = 1e8;

LinearSieve<N> sieve;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int q;
	cin >> q;
	while (q--) {
		int n;
		cin >> n;
		cout << sieve.pr[n - 1] << '\n';
	}
	return 0;
}

#define PROBLEM "https://www.spoj.com/problems/TDKPRIME/"

#include <bits/stdc++.h>

using namespace std;


template <int N> struct LinearSieve {
	std::bitset<N> pri;
	std::vector<int> pr;
	
	LinearSieve() {
		pri.set();
		pri[0] = pri[1] = 0;
		for (int i = 2; i < N; ++i) {
			if (pri[i]) 
				pr.push_back(i);
			for (int j = 0; j < (int)pr.size() && i * pr[j] < N; ++j) {
				pri[i * pr[j]] = 0;
				if (i % pr[j] == 0) 
					break;
			}
		}
	}
};

const int N = 1e8;

LinearSieve<N> sieve;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int q;
	cin >> q;
	while (q--) {
		int n;
		cin >> n;
		cout << sieve.pr[n - 1] << '\n';
	}
	return 0;
}

Back to top page