PMDY - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Game of Primes

Authors: Suraj Verma and Shreyash Choudhary
Testers: Rishabh Rathi and Aditya Sharma

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Number Theory

PROBLEM:

Today you got a phone call from your crush. She was solving a problem on Codechef but wasn’t able to solve it. Your task is to solve that problem as she asked you. You can’t say no to her.

The problem statement was to find the smallest number K such that there are N Prime numbers between 1 and K (both inclusive) and then output the XOR of first K natural numbers.

EXPLANATION:

First of all, precompute all the prime numbers using the Sieve of Eratosthenes.
Then just get the N^{th} prime number and that number will be your K.

Now just find the XOR of all the numbers from 1 to K and print it.

SOLUTIONS:

Setter's Solution - CPP 
#include <bits/stdc++.h>  
using namespace std;

const long long MAX_SIZE = 1300000;
vector<long long>isprime(MAX_SIZE , true);
vector<long long>prime;
vector<long long>SPF(MAX_SIZE);

// function generate all prime number less then N in O(n)
void manipulated_seive() {
	// 0 and 1 are not prime
	isprime[0] = isprime[1] = false;

	// Fill rest of the entries
	for (long long int i=2; i<MAX_SIZE ; i++) {
		// If isPrime[i] == True then i is prime number
		if (isprime[i]) {
			// put i into prime[] vector
			prime.push_back(i);

			// A prime number is its own smallest prime factor
			SPF[i] = i;
		}
		for (long long int j = 0; j < (int)prime.size() && i*prime[j] < MAX_SIZE && prime[j] <= SPF[i]; j++) {
			isprime[i*prime[j]] = false;

			// put smallest prime factor of i*prime[j]
			SPF[i*prime[j]] = prime[j] ;
		}
	}
}


// Method to calculate xor
long long computeXOR(long long n) {
	if (n % 4 == 0)
		return n;
	if (n % 4 == 1)
		return 1;
	if (n % 4 == 2)
		return n + 1;
	return 0;
}


int main() {
	ios_base::sync_with_stdio(0);  cin.tie(0);
	long long t, n;
	cin>>t;
	manipulated_seive();

	while(t--) {
		cin>>n;
		cout<<computeXOR(prime[n-1])<<endl;
	}

	return 0;
}
Tester's Solution - Python 
# Function to generate N prime numbers using Modified Sieve of Eratosthenes in O(n) 
def manipulated_seive(): 
	N = 1300000
	isprime = [True] * N
	prime = []
	SPF = [None] * N

	isprime[0] = isprime[1] = False

	for i in range(2, N):
		if isprime[i] == True:
			prime.append(i)
			SPF[i] = i 

		j = 0
		while (j < len(prime) and i * prime[j] < N and prime[j] <= SPF[i]):
			isprime[i * prime[j]] = False
			SPF[i * prime[j]] = prime[j]
			j += 1

	return prime


# Function to calculate xor from 1 to n in O(1)
def computeXOR(n):
	# if n is multiple of 4
	if n % 4 == 0 :
		return n

	# If n % 4 gives remainder 1
	if n % 4 == 1 :
		return 1

	# If n%4 gives remainder 2
	if n % 4 == 2 :
		return n + 1

	# If n%4 gives remainder 3
	return 0

primes = manipulated_seive()

t = int(input())
for i in range(t):
	n = int(input())
	k = primes[n-1]
	# print(k)
	print(computeXOR(k))

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. :smile: