Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

Nisiyama_Suzune's blog

By Nisiyama_Suzune, 16 months ago, In English,

This short article is mainly focused on the linear sieve and its various applications in competitive programming, including a brief introduction on how to pick out primes and a way to calculate multiple values of multiplicative functions.

Sieve of Eratosthenes

While this name may sound scary, the sieve of Eratosthenes is probably the simplest way to pick out all the primes in a given range from 1 to n. As we already know, one of the properties that all primes have is that they do not have any factors except 1 and themselves. Therefore, if we cross out all composites, which have at least one factor, we can obtain all primes. The following code demonstrates a simple implementation of the said algorithm:

std::vector <int> prime;
bool is_composite[MAXN];

void sieve (int n) {
	std::fill (is_composite, is_composite + n, false);
	for (int i = 2; i < n; ++i) {
		if (!is_composite[i]) prime.push_back (i);
		for (int j = 2; i * j < n; ++j)
			is_composite[i * j] = true;
	}
}

As we can see, the statement is_composite[i * j] = true; crosses out all numbers that do have a factor, as they are all composites. All remaining numbers, therefore, should be prime. We then check for those primes and put them into a container named prime.

Linear sieve

It can be analyzed that the method above runs in complexity (with the Euler–Mascheroni constant, i.e. ). Let us take a minute to consider the bottleneck of such sieve. While we do need to cross out each composite once, in practice we run the inner loop for a composite multiple times due to the fact that it has multiple factors. Thus, if we can establish a unique representation for each composite and pick them out only once, our algorithm will be somewhat better. Actually it is possible to do so. Note that every composite q must have at least one prime factor, so we can pick the smallest prime factor p, and let the rest of the part be i, i.e. q = ip. Since p is the smallest prime factor, we have i ≥ p, and no prime less than p can divide i. Now let us take a look at the code we have a moment ago. When we loop for every i, all primes not exceeding i is already recorded in the container prime. Therefore, if we only loop for all elements in prime in the inner loop, breaking out when the element divides i, we can pick out each composite exactly once.

std::vector <int> prime;
bool is_composite[MAXN];

void sieve (int n) {
	std::fill (is_composite, is_composite + n, false);
	for (int i = 2; i < n; ++i) {
		if (!is_composite[i]) prime.push_back (i);
		for (int j = 0; j < prime.size () && i * prime[j] < n; ++j) {
			is_composite[i * prime[j]] = true;
			if (i % prime[j] == 0) break;
		}
	}
}

As is shown in the code, the statement if (i % prime[j] == 0) break; terminates the loop when p divides i. From the analysis above, we can see that the inner loop is executed only once for each composite. Hence, the code above performs in O(n) complexity, resulting in its name — the 'linear' sieve.

Multiplicative function

There is one specific kind of function that shows importance in the study of number theory — the multiplicative function. By definition, A function f(x) defined on all positive integers is multiplicative if it satisfies the following condition:

For every co-prime pair of integers p and q, f(pq) = f(p)f(q).

Applying the definition, it can be shown that f(n) = f(n)f(1). Thus, unless for every integer n we have f(n) = 0, f(1) must be 1. Moreover, two multiplicative functions f(n) and g(n) are identical if and only if for every prime p and non-negative integer k, f(pk) = g(pk) holds true. It can then be implied that for a multiplicative function f(n), it will suffice to know about its representation in f(pk).

The following functions are more or less commonly used multiplicative functions, according to Wikipedia:

  1. The constant function I(pk) = 1.
  2. The power function Ida(pk) = pak, where a is constant.
  3. The unit function ε(pk) = [pk = 1] ([P] is 1 when P is true, and 0 otherwise).
  4. The divisor function , denoting the sum of the a-th powers of all the positive divisors of the number.
  5. The Möbius function μ(pk) = [k = 0] - [k = 1].
  6. The Euler's totient function φ(pk) = pk - pk - 1.

It is interesting that the linear sieve can also be used to find out all the values of a multiplicative function f(x) in a given range [1, n]. To do so, we have take a closer look in the code of the linear sieve. As we can see, every integer x will be picked out only once, and we must know one of the following property:

  1. x is prime. In this case, we can determine the value of f(x) directly.
  2. x = ip and p does not divide i. In this case, we know that f(x) = f(i)f(p). Since both f(i) and f(p) are already known before, we can simply multiply them together.
  3. x = ip and p divides i. This is a more complicated case where we have to figure out a relationship between f(i) and f(ip). Fortunately, in most situations, a simple relationship between them exists. For example, in the Euler's totient function, we can easily infer that φ(ip) = pφ(i).

Since we can compute the function value of x satisfying any of the above property, we can simply modify the linear sieve to find out all values of the multiplicative function from 1 to n. The following code implements an example on the Euler's totient function.

std::vector <int> prime;
bool is_composite[MAXN];
int phi[MAXN];

void sieve (int n) {
	std::fill (is_composite, is_composite + n, false);
	for (int i = 2; i < n; ++i) {
		if (!is_composite[i]) {
			prime.push_back (i);
			phi[i] = i - 1;					//i is prime
		}
		for (int j = 0; j < prime.size (); ++j) {
			is_composite[i * prime[j]] = true;
			if (i % prime[j] == 0) {
				phi[i * prime[j]] = phi[i] * prime[j];	//prime[j] divides i
				break;
			} else {
				phi[i * prime[j]] = phi[i] * phi[prime[j]];	//prime[j] does not divide i
			}
		}
	}
}

Extension on the linear sieve

Well, it might not always be possible to find out a formula when p divides i. For instance, I can write some random multiplicative function f(pk) = k which is difficult to infer a formula with. However, there is still a way to apply the linear sieve on such function. We can maintain a counter array cnt[i] denoting the power of the smallest prime factor of i, and find a formula using the array since . The following code gives an example on the function I've just written.

std::vector <int> prime;
bool is_composite[MAXN];
int func[MAXN], cnt[MAXN];

void sieve (int n) {
	std::fill (is_composite, is_composite + n, false);
	for (int i = 2; i < n; ++i) {
		if (!is_composite[i]) {
			prime.push_back (i);
			func[i] = 1; cnt[i] = 1;
		}
		for (int j = 0; j < prime.size (); ++j) {
			is_composite[i * prime[j]] = true;
			if (i % prime[j] == 0) {
				func[i * prime[j]] = func[i] / cnt[i] * (cnt[i] + 1);
				cnt[i * prime[j]] = cnt[i] + 1;
				break;
			} else {
				func[i * prime[j]] = func[i] * func[prime[j]];
				cnt[i * prime[j]] = 1;
			}
		}
	}
}

Example problems

The Embarrassed Cryptographer

Link

Solution: Simply applying the linear sieve will be enough.

Farey Sequence

Link

Solution: Notice that Δ F(n) = F(n) - F(n - 1) is multiplicative and Δ F(pk) = pk - pk - 1. Then the linear sieve will come in handy to solve the problem.

 
 
 
 
  • Vote: I like it  
  • +226
  • Vote: I do not like it  

»
16 months ago, # |
  Vote: I like it +2 Vote: I do not like it

I don't understand anything. But it looks like something useful so upvote for you.

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

@Nisiyama_Suzune do you have any origin reference for this linear sieve? It's amazing it's not well known (as far I know) in the competitive programming world.

»
15 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone explain why are we doing if (i % prime[j] == 0) break;

Finally I understood it , Once we reach a number i * prime[j] where i % prime[j] == 0 we know that i * prime[j + 1] will also have prime[j] as the smallest prime divisor.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hello there,

i usually write sieve in this style:

for(i=4;i<mxn;i=i+2) prime[i]=1; // erasing the even number
for(i=3;i*i<mxn;i=i+2){ //computing only odd number
    if(prime[i]==0){ //if i is prime then
        for(j=i*i;j<mxn;j=j+i+i){ // erasing only odd number which is composite
            prime[j]=1;
        }
    }
}

isn't the amortized complexity of this algorithm O(n)? or do i understand something wrong?

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Based on my knowledge, only crossing out even numbers first does not make a sieve O(n), so I doubt its correctness on complexity. For instance, 105 will be visited multiple times (for 3, 5 and 7) in your code. Therefore, I think your code still performs in . However, I do think there is not too much difference between O(n) and in sieves. The reason why I introduced the algorithm is mainly that it can help to compute the multiplicative functions, where other sieves are less likely to do so.

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      That code in particular is O(nloglogn) since it uses the sum of inverse of primes which is bounded by O(loglogn).

»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it

In your Euler's function, when X = iP and P does not divide i, shouldn't it be phi[i * prime[j]] = phi[i] * phi[prime[j]]? Since j is only the index of the prime.

Awesome blog btw. Keep on with the math notes!

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can you please share code for mobius function using linear sieve?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the code for Phi function :
for (int j = 0; j < prime.size (); ++j) { It should be j < prime.size() && i*prime[j] < n
Really Awesome blog :) ! Thanks, And Keep Writing

»
8 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

In the Extension on the linear sieve, in the i%prime[j]==0 condition, shouldn't it be func[i * prime[j]] = func[i / pow(prime[j],cnt[i])] * func[pow(prime[j],cnt[i] + 1)] ?

  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Its correct in the article. Since f(p^k) = k and also f(i/p^k) = f(i) / f(p^k). (this can be proved as; f(i) = f(p^k * i/p^k) => f(i) = f(p^k) * f(i/p^k) => f(i/p^k) = f(i)/f(p^k))

    Note: gcd(p^k, i/p^k) = 1

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the easy problem!! The Embarrassed Cryptographer

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Precompute all primes till 106, then for every prime less than L check if it divides K. O(|K| * pi) for each test case where pi is the count of primes less than L.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes but ain't 4 <= K <= 10^100?, how can I do that in c++ without implementing my own BigNum divide/multiply method. Thanks for answering btw :)

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        You can convert a string into an integer with taking modulo.

        int get_rem(string s, int mod) {
            int x = 0;
            for (int i = 0; i < s.size(); i++) {
                x = (x * 10 + s[i] - 48) % mod;
            }
            return x;
        }
        
»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Even though the linear sieve has a time complexity of O(n), still, the time taken to iterate through the vector of primes, makes it slower when compared to the classic sieve of eratosthenes. In practice, the classic one with a few modifications like crossing out multiples of 2 in a separate loop and then only dealing with the odd numbers in the "main" loop, is faster.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Proof?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I benchmarked it. You can check it as well.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Link?

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I benchmarked locally, no link sorry. You can do and check if you feel skeptical. Time Complexity improvements doesn't always translate to actual execution time improvements.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Can you put the code you wrote in a pastebin or something? It would save a lot of time for others to verify.

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I'm not sure if that counts as good benchmarking, but here goes : old vs new seive

              • »
                »
                »
                »
                »
                »
                »
                »
                4 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Thanks. I slightly changed the old sieve in your code to use i*i instead of i*2. Also made the time measurement more accurate. Also made N = 1e8.

                ajkdrag, looks like you were wrong. Linear sieve is almost twice as fast.

                https://ideone.com/HMjE7c

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 weeks ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 weeks ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  I had Aitken's sieve in my codebase, since I read somewhere that it is very fast. I also benchmarked that implementation, and it turned out really slow. So I decided to play a little bit more, to find a new implementation for my codebase: https://ideone.com/I4piBg. Optimized means, that I skip all even numbers (don't even allocate memory for them, i.e. is_prime[i] checks if i*2+1 is prime).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 weeks ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  Here is the pastebin link : https://pastebin.com/exBZdLJK

                  I checked on Ideone, the time was more for the linear sieve (idk why?)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Don't use Java. The library performance is really bad. Especially for TreeSet/TreeMap.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  But I didn't even use TreeSet/TreeMap, I simply used an ArrayList, which is basically an Array itself, to store the primes, and yet the time difference is huge. How so?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This is quite nice, though I have a small issue with calling it the "linear sieve", especially since there is something called the linear sieve from math which is quite different from what is described here (see for example this blog post by Terry Tao. If this technique is actually related to this, I would be very curious how it is the case that this is related to the ideas behind the linear sieve the link discusses.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Just a note, I think your code for calculating the totient function has an edge case where you don't calculate phi(1). I think you need to set phi[1]=1 at the beginning of your loop.