Prime Range Queries

OFZ · February 23, 2021, 8:27pm

So given a problem that goes something like how many primes are in the range [a, b] where 1 <= a, b <= 1e9, or some other large number (where you simply cannot store it in a array of such size), how would you solve that?

jessechoe10 · February 23, 2021, 8:34pm

Could you provide the source of this problem to make sure you’re not asking this during a live contest to cheat?

OFZ · February 23, 2021, 8:36pm

Benq · February 25, 2021, 12:06am

github.com

bqi343/USACO/blob/1661eb4063475e946a9443bd61b5cf21e6620b18/Implementations/content/number-theory (11.1)/Primality/PrimeCnt.h

/**
 * Description: Counts number of primes up to $N$. Can also count 
 	* sum of primes. For faster performance, only consider odd values
 	* of \texttt{i} in the loops involving \texttt{B[i]}.
 * Time: $O(N^{3/4}/\log N)$, works for $N=10^{11}$.
 * Source: https://www.topcoder.com/single-round-match-741-editorials/
 	* also see faster https://codeforces.com/group/ZFgXbZSjvp/contest/274852/submission/76443529
 	* https://blog.csdn.net/bestFy/article/details/80100244
 * Verification: 
 	* https://codeforces.com/group/ZFgXbZSjvp/contest/274852/problem/A
 	* https://www.spoj.com/problems/DIVCNT3/
 */

#include "Sieve.h"

ll N; vl A, B; // sieve should store primes up to sqrt(N) and one more
ll primeCnt() { // A[i] stores # primes <= i
	int SN = sqrt(N);  A = B = vl(SN+1);
	FOR(i,1,SN+1) A[i] = i-1, B[i] = N/i-1;
	vd in(SN+1); FOR(i,1,SN+1) in[i] = 1.0/i;

This file has been truncated. show original