Tanmoy1228's blog

Number Theory Problem (Prime Number Problem)
By Tanmoy1228, history, 9 years ago, In English

Problem:

A certain strange mathematician, Rasyak, considers a particular set of prime numbers beautiful. He also calls a composite number beautiful, if it is divisible by at least one prime number in his chosen set of beautiful primes. Given Rasyak’s set of M beautiful primes and an integer N, you have to find the number of beautiful numbers (both primes and composites) between 1 and N. For example, given a set of 2 beautiful primes, {2, 5}, there are 6 beautiful numbers between 1 and 10 (i.e. 2, 4, 5, 6, 8 and 10).

Input

The first line of the input gives the number of test cases, T (1 <= T <= 100). T test cases follow. Each will consist of one line containing a single integer M, followed by a line containing M space-separated prime numbers mi, followed by another line containing a single integer N.

1 <= M <= 25

1 <= mi <= 1000

1 <= N <= 2*10^9

Output

For each test case, output one line containing a single integer X, where X is the number of beautiful numbers between 1 and N.

Input

3

2
2 5
10

3
2 5 13
100

25
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
2000000000

Output

6

63

1759360857

How can i solve this problem???

any idea????

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

Comments Comments (3)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not pretty sure but I think it can be solved with inclusion exclusion principle I once read what is it about and I think it is the way to solve this problem .

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Well I came up with the following:

First let's simplify the problem and suppose that m is equal to 1, so the answer will be floor(N/m[0]), right?

Now lets see the general case where m is <= 25:

Lets do the case 3 2 5 13 100

First lets solve for 2: 100/2=50 (lets call these 50 numbers A)

Now lets solve for 5: 100/5=20 (lets call these 20 numbers B) But out of those 20 numbers there are some of them that are divisible by 2 and since those will be repeated we want to delete them. How to do that? We apply basic inclusion exclusion theory, if we want to get the union of set A and set B the answer is A+B-intersection(A,B), right??

Now let's apply that to this, suppuse A is all the numbers divisible by 2, and B all the numbers divisible by 5, so the intersection would be all numbers divisible by 2 and 5 AKA 2*5=10.

So if that same case had m=2 instead of 3 (suppuse we take away 13) the answer would be 50+20-10 = 60

And finally lets consider 13 100/13=7 (lets call these 7 numbers C)

So, by inclusion exclusion A+B+C-intersection(A,B)-intersection(B,C)-intersection(A,C)+intersection(A,B,C) 50+20+7-10-1-3+0 = 63

Overall time complexity is 2^M, but in reality you can reduce the time complexity considerably if by multiplying the numbers you already obtained a number bigger than N, just ignore it (since it will produce 0), I estimate around 10^6 iterations needed if done right.

In previous case for intersection(A,B,C) we need to obtain A*B*C=130 and since that is bigger than N we can ignore everything from that branch onward (Assuming you implement it recursively).

→ Reply