Блог пользователя Nisiyama_Suzune

Автор Nisiyama_Suzune, 7 лет назад, По-английски

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);
	phi[1] = 1;
	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 () && i * prime[j] < n; ++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);
	func[1] = 1;
	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 () && i * prime[j] < n; ++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.

  • Проголосовать: нравится
  • +226
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

@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.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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!

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve the easy problem!! The Embarrassed Cryptographer

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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;
        }
        
»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Nisiyama_Suzune you forgot to mention the following things in your blog:

  1. In your functions to compute euler's totient function and the multiplicative function you didn't write phi[i] = 1 and func[i] = 1 respetively.

  2. In both of them you didn't break the loops if i * prime[j] >= n.

  3. You used a further simplification of the formula for f(ip) which you didn't mention i.e., .

It'll be helpful for future readers if you can make these changes in the blog.

BTW, a really good blog.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Regarding 3.: This division trick doesn't actually work when f(pk) = 0 for some k > 0. In that case you need the original multiplication. It's probably easiest to keep track of both cnt(i) and pcnt(i) so that the division i / pcnt(i) can be done fast.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Fixed. Thank you!

»
6 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

It's possible to make this much faster by storing the smallest prime factor of each number while sieving (instead of the current bool). That way you can avoid the expensive modulo check in the inner loop and just do if(primes[j] == spf[i]) break; instead.

This gave a ~4x speedup on my machine.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    This optimization doesn't work for me. It actually makes the sieve significantly slower. Am I missing something?

    See benchmark here: https://ideone.com/z11b4t

    For 1e8, I get .34 without that optimization, and .44 with that optimization. I suspect a large reason why is that doing that optimization requires switching your sieve from a boolean to an integer.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain in the linear sieve algorithm "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." I don't understand why stoppping when prime divides i allows me to pick out each composite once

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    In this way we visit each composite x = i*prime[j] only when i is the greatest number that divides it (exluding x itself)*. Therefore, since for every number x there is only 1 such number (its greatest divisor exluding x), we will visit each composite exactly once.

    *Proof: We will prove that if i = k*prime[j] (i.e. i%prime[j] = 0), then i is not the greatest divisor of x = i*prime[j+1] (excluding x). Well, since x = i*prime[j+1] and i = k*prime[j], we get that x = k*prime[j]*prime[j+1]. Therefore k*prime[j+1] divides x, and k*prime[j+1] > k*prime[j] = i. QED

    Example: (I ran the code given for n = 50 and next to each i I wrote all x = i*prime[j] that were visited in the inner loop. Notice that every composite is only visited once) 2: 4| 3: 6 9| 4: 8|
    5: 10 15 25| 6: 12| 7: 14 21 35 49| 8: 16| 9: 18 27| 10: 20| 11: 22 33| 12: 24| 13: 26 39| 14: 28| 15: 30 45| 16: 32| 17: 34| 18: 36| 19: 38| 20: 40| 21: 42| 22: 44| 23: 46| 24: 48| 25: ... (for i = 25 to 49, no x were visited)

»
10 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

HELP, Δ F(n) = F(n) - F(n - 1) is multiplicative and Δ F(p^k) = p^k - p^(k - 1) How do we prove these relations in the second problem?

»
7 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I didn't understand the extension on the linear sieve part: basically, The relation between f(ip) and f(i),f(p). Can someone please elaborate on that