what’s the most efficient way to check if a number is prime???
the algorithm we will use here is segmented sieve :
have a look :-
The essence of the algorithm used by a sieve is removing the factors of the number. eg. first we remove the factors of 2 ie. 4,6, 8,10… , and then factors of 3 ie. 9 12, 15… so on and so forth.
But applying the same logic for bigger constraints would result in TLE. Thus segment sieve comes into picture.
The segment sieve also applies the same logic BUT on the segment. Thus, Segment Sieve works only if the segment length is within manageable constraints.
Consider a segment given by [m,n]. We remove all the factors which are greater than m but less than n. To check whether a number between m and n is a factor, we use a boolean array(is_factor)…whereis_factor[i] denotes whether the number which at a offset of i from lower bound of the segment(m). Now the factors are eliminated by considered all the numbers which are less than the sqrt(m).
Let’s consider an example to illustrate my point.
Suppose m=1000 and n=1100 So we will remove all the factors of x( where x ranges from 2 to sqrt(1000)).
Therefore, When x=2—> 1000,1002,1004,…1100 get crossed…(corresponding is_factor gets marked).
When x=3 --> 1002,1005,1008,…1098 get crossed… And the process continues.
So the ones which remain unmarked are the primes in the interval [m,n].
I think with each problem, we have different algorithm to check whether it is a prime or not. Example: With a problem: Count prime numbers in range [x,y], which is x,y<=10^8, you can use erathos with a complexity of making array is O(n) and O(1) for each query. Another way, you can use algorithm by check any number in [2…sqrt(x)] or use +2 +4 for less complexity.