Saturday, February 14, 2015

Problem discussion: Facebook Hacker Cup 2015 Round 1 - Homework

It's been a long time since I last wrote on this blog and a lot has happened since then. The most important of all is that my personal website is up at and consequently this blog can now be accessed at Also, you can now reach through email at

Let's get down to business now. The online part of Facebook Hacker Cup 2015 concluded recently and the top 25 contestants have been selected to compete in the onsite finals. The problem I am writing about in this post appeared in the Round 1 (there were 3 rounds).

The title of the problem is "Homework" and here is the abridged statement:
Given three integers \(A\), \(B\) and \(K\), find the number of integers in range \(\big[A, B\big] \) that have a "primacity" of \(K\). Primacity of a number \(N\) is defined as the number of distinct prime factors of \(N\). You have to process \(T\) such queries.
The constraints are as follows:
  • \(2 \le A \le B \le 10^{7}\)
  • \(1 \le K \le 10^{9}\)
  • \(1 \le T \le 100\)
The first thing to notice here is that the number of prime factors of \(10^{7}\) is not very large. In fact, it is at most \(8\). So, the maximum primacity of a number within the given constraints is \(8\). To know more about this read about Primorial on Wikipedia.

We can modify the sieve algorithm to calculate the primacity of each number in the range \( \big[1, 10^{7}\big] \) in the following way: whenever you "cross-out" a number designating it as non-prime, increment the value at that position. This works because for any number \(x\), the primacity is equal to the number of primes less that \(x\) that divide it which is the same the number of times it is crossed out in the sieve algorithm.

Now that we know the primacity every possible number within the constraints, we need to think about how to answer the queries efficiently. Notice that the answer can be expressed as follows
answer = answer for \(\big[1, B\big]\) \(-\) answer for \(\big[1, A - 1\big]\)
We can answer queries in \(\mathcal{O}(1)\) time with some pre-computation. The pre-computation can be done this way
Let c[n][p] denote the number of integers in [1, n] with primacity p then,
c[n][p] = c[n - 1][p] + 1   if primacity of n is p
c[n][p] = c[n - 1][p]       if primacity of n is not p
We do this pre-processing for all possible values of primacity and answer each query in \(\mathcal{O}(1)\) time.

You can test the correctness of your solutions by submitting it in the Codeforces Gym (login required) or you can download the official input and output files and test your solution against them. Here's my C++ code (shortened). You can find the full code on GitHub.

const int N = 10000001;

bool mark[N];
int p[N], ct[N][8];

int main() {
  mark[1] = false;
  for (int i = 2; i < N; ++i) {
    if (mark[i]) continue;
    for (int j = 1; i * j < N; ++j) {
      mark[i * j] = true;
      p[i * j]++;
  for (int i = 2; i < N; ++i) {
    for (int j = 0; j < 8; ++j)
      ct[i][j] = ct[i - 1][j];
    ct[i][p[i] - 1]++;
  int t, a, b, k;
  scanf("%d", &t);
  for (int tt = 1; tt <= t; ++tt) {
    scanf("%d %d %d", &a, &b, &k);
    printf("Case #%d: ", tt);
    if (k > 8) printf("0\n");
    else {
      int ans = ct[b][k - 1] - ct[a - 1][k - 1];
      printf("%d\n", ans);
  return 0;

I will be back next week with the next problem "Autocomplete" from the same round.

Thanks for reading!


  1. You should be worried about Facebook hacking. Before you dismiss the threat check out Free Random Password Generator, this article which might just change your mind. All people use strong passwords for all online accounts. This also applies to the websites they create.

  2. I generally want the quality substance, and this thing I found in your post. I'm truly thankfull to you for this post.keep sharing this in future. Hire a professional hacker

  3. Thanks for publishing such great information. You are doing such a great job. This information is very helpful for everyone. Keep it up. Thanks. Social Media Hackers For Hire

  4. Wow! Thank you! I constantly wanted to write on my site something like that. Can I take a portion of your post to my website? Best genuine hackers for hire service provider.

  5. I will share it with my other friends as the information is really very useful. Keep sharing your excellent work. Hire a hacker

  6. It’s actually a great and helpful piece of info. I’m happy that you just shared this helpful info with us. Please keep us informed like this. Thanks for sharing! best hire a hacker to get a password service provider.

  7. It’s great to come across a blog every once in a while that isn’t the same out of date rehashed material. Fantastic read.Best i need a good hacker to help me repair my credit score service provider

  8. After a long time, I read a very beautiful and very ismportant article that I enjoyed reading. I have found that this article has many important points, I sincerely thank the admin of this website for sharing it.Best i need a good hacker to help me repair my credit score service provider

  9. It’s great to come across a blog every once in a while that isn’t the same out of date rehashed material. Fantastic read. Best i need a hacker urgently Services Provider