Finding numbers divisible by primes in a given range

Question

The problem statement (Codeforces# 385C) is this:

We are given a sequence of \$n\$ numbers, i.e. \$x_i\$ and \$m\$ queries to find how many of these are divisble by primes between two given numbers (not necessarily prime) \$l_i\$ and \$r_i\$ (inclusive).

Constraints are: \1ドル\le n\le 10^6, 2\le x_i \le 10^7, 2\le m \le 50000, 2\le l_i\le r_i \le 2x10^9\$

My approach is to create a map xcnt which contains unique \$x_i\$ and their counts so as to reduce repeated efforts. I also find the maximum \$x_i\$ as maxx. Now I sieve all odd numbers from 3 in a boolean array using Sieve of Erathosthenes and at the same time creating a map primes and a list primelist which contain the prime numbers and the map just contains key value pair as prime number and index to list.

Next, I create a Binary Index Tree/Fenwick Tree which is indexed by the prime numbers' index, i.e. BIT[1] contains the count of numbers divisible by 0^th prime number which I consider as 2, then BIT[2] contains sum of counts of numbers divisible by 2 and 3 and so on according to design of Fenwick Tree. Finally when I am given integers \$l_i\$ and \$r_i\,ドル I use binary search (builtin) to find the smallest and largest prime number in this range and then use BIT to find the sum of counts.

My Java based solution (works perfectly):

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;
import java.util.TreeMap;
public class P385C {
 public static void main(String[] args) {
 Scanner in = new Scanner(System.in);
 int n = in.nextInt();
 int[] x = new int[n];
 //count of x
 HashMap<Integer, Integer> xcnt = new HashMap<>();
 //max of x
 int maxx = 0;
 for (int i = 0; i < n; i++) {
 x[i] = in.nextInt();
 //if not in map add (x[i],0)
 if (!xcnt.containsKey(x[i])) xcnt.put(x[i], 0);
 //xcnt[x[i]]++
 xcnt.put(x[i], xcnt.get(x[i]) + 1);
 if (x[i] > maxx) maxx = x[i];
 }
 int m = in.nextInt();
 boolean[] notprime = new boolean[(maxx - 3) / 2 + 1];
 //0->3,1->5,2->7,3->9,4->11,5->13,6->15,7->17,...n-1->2n+3=maxx
 //map of (pn,n) [pn=nth prime number n=0,1,2..]
 TreeMap<Integer, Integer> primes = new TreeMap<>();
 List<Integer> primelist = new ArrayList<>();
 int ind = 1;
 primes.put(2, 0);
 primelist.add(2);
 for (int i = 0; 2 * i + 3 <= maxx; i++) {
 if (!notprime[i]) {
 long num = 2 * i + 3;
 for (long j = num * num; j < maxx; j += num)
 if (j % 2 == 1) notprime[(int) ((j - 3) / 2)] = true;
 primes.put((int) num, ind++);
 primelist.add((int) num);
 }
 }
 BIT bit = new BIT(primes.size() + 1);
 for (int xs : xcnt.keySet()) {
 for (int p : primelist) {
 // if p>xs no more divisibility now
 if (p > xs) break;
 // if xs%p then we add xcnt[xs] to f(p) in BIT by getting index from primes map
 if (xs % p == 0) bit.add(primes.get(p), xcnt.get(xs));
 }
 }
 for (int i = 0; i < m; i++) {
 int l = in.nextInt();
 int r = in.nextInt();
 if (l <= maxx) {
 //get just next or equal prime
 int pmin = primes.ceilingKey(l);
 //get just previous or equal prime
 int pmax = primes.floorKey(r);
 System.out.println(bit.sumRange(primes.get(pmin), primes.get(pmax)));
 continue;
 }
 System.out.println(0);
 }
 in.close();
 }
 static class BIT {
 int[] bit;
 public BIT(int n) {
 bit = new int[n];
 }
 public int getSum(int ind) {
 int sum = 0;
 ind++;
 while (ind > 0) {
 sum += bit[ind];
 ind -= ind & -ind;
 }
 return sum;
 }
 public void add(int ind, int val) {
 ind++;
 while (ind < bit.length) {
 bit[ind] += val;
 ind += ind & -ind;
 }
 }
 public int sumRange(int i, int j) {
 return getSum(j) - getSum(i - 1);
 }
 }
}

Problem

• I did not think so but this solution though working correctly is not fast enough, according to my calculations I believe my complexity is \$O(n(\log{n})(\log\log{n})+m(\log{n}+\log{P})+P\log{P})\$ where \$P\$ (664,579~10^7) is the count of primes below maximum x so total operations are of order 10^8 which I think can be solved under a second under present computers (given time limit is 2 seconds).
• I would also like to welcome any other improvements that I could make or any other suggestions.

Answer 1

General comments

This is a monolithic block of code. Even some newlines to break it up would help readability, and really I think it would benefit from being split into several methods.

---

In my opinion the existing comments are unnecessary. Comments shouldn't tell me what the code does: the code tells me that. They should tell me why. For example, why does the sieve run up to (maxx - 3) / 2?

---

Performance

Following on from that previous remark, I would expect that the sieve would run up to the largest prime necessary. Deciding what's necessary is interesting: you can narrow it down quite a lot at the expense of slightly complicating the code, and since performance is an issue you probably want to narrow it.

• It's not necessary to deal with any prime greater than the largest one used by the queries, so it might be worth reading and caching queries before pre-processing the sequence.
• You can factor maxx with a list of primes up to sqrt(maxx) (inclusive).

---

You should never iterate through a map's keySet and look up the keys inside the loop. Use entrySet. That's even more important with TreeMap, which doesn't even have average-case constant time lookup. So

 for (int xs : xcnt.keySet()) {
 for (int p : primelist) {
 // if p>xs no more divisibility now
 if (p > xs) break;
 // if xs%p then we add xcnt[xs] to f(p) in BIT by getting index from primes map
 if (xs % p == 0) bit.add(primes.get(p), xcnt.get(xs));
 }
 }

should be

 for (Map.Entry<Integer, Integer> seqEntry : xcnt.entrySet()) {
 int xs = seqEntry.getKey();
 for (Map.Entry<Integer, Integer> primeEntry : primes.entrySet()) {
 int p = primes.getKey();
 // if p>xs no more divisibility now
 if (p > xs) break;
 // if xs%p then we add xcnt[xs] to f(p) in BIT by getting index from primes map
 if (xs % p == 0) bit.add(primeEntry.getValue(), seqEntry.getValue());
 }
 }

(Actually, if you follow my previous suggestion of only calculating primes up to sqrt(maxx) then you need to insert a phase because when you factor x_i you may find entries which are primes greater than that limit and need inserting; and you would be iterating over a flat list of primes then updating a TreeMap<Integer, Integer> which will later be converted into a BIT, but that's not the point).

---

The BIT class is a nice optimisation for lookups, but the way it's built is expensive. This is a further argument for an extra phase: if you first accumulate direct counts in a map then the BIT can be accumulated in a single pass with a running sum, rather than updating many entries for each x_i.

• RE60K: Thanks for suggestion Peter, Infact that improved its performance quite well, code. Alas it couldn't pass the tests. I also tried C++ implementation, but finally I had to change the whole algorithm. Thanks for the help.
• Peter Taylor: @Aliester, that's only an optimisation if you're doing it by hand rather than by computer.
• Adrian: @PeterTaylor I took another look at the code and I must be pretty tired. I had originally read it as a manual iteration through all values of "x"