Finding intersections in a given range ?

[mohamed el teir]

assume array of N (N<=100000) elements a1, a2, ... ,an, and you are given range in it L, R where 1<=L<=R<=N, you are required to get number of values in the given range which are divisible by at least one number from a set S which is given also, this set can be any subset of {1,2,...,10}. a fast way must be used because it may ask you for more than one range and more than one S (many queries Q, Q<=100000), so looping on the values each time will be very slow.

i thought of storing numbers of values divisible by each number in the big set {1,2,...,10} in 10 arrays of N elements each, and do cumulative sum to get the number of values divisible by any specific number in any range in O(1) time, for example if it requires to get number of values divisible by at least one of the following: 2,3,5, then i add the numbers of values divisible by each of them and then remove the intersections, but i didn't properly figure out how to calculate the intersections without 2^10 or 2^9 calculations each time which will be also very slow (and possibly hugely memory consuming) because it may be done 100000 times, any ideas ?

 

[Fooality]

Well, the main I need to make sure you are aware of is the complexity of the factorization a number into its prime factors, which is so hard its used in encryption schemes. You are pretty much left with brute force methods. One thing that isn't hard to do if S is small is to produce the multiples of numbers in your set S that might fall within the range given, then you are left with a set intersection problem which has pretty fast implementations in dynamic programming and in data structures like red black trees.