KPRIMESB  Almost Prime Numbers Again
Almost Prime Numbers are composite numbers which are not divisible by certain prime numbers. Given K prime numbers and an integer N, find out the number of Almost Prime Numbers (i.e. composite numbers not divisible by any of the given K prime numbers) that are not greater than N.
Input
First line of input consists of an integer T (1<=T<=1000), denoting the number of test cases. Then T test cases follow. Each case begins with a line containing two integers N (0<=N<=10^6) and K (1<=K<=10). The next line contains K space separated prime numbers. All the prime numbers are guaranteed to be less than 50.
Output
For each test case, output a single line in the format Case X: Y, where X denotes the test case number and Y denotes the number of Almost Prime Numbers that are not greater than N.
Example
Input: 2 1000 3 2 3 5 49 3 2 3 5 Output: Case 1: 100 Case 2: 1
hide comments
citizendot:
20221206 04:22:17
@mehmetin, I can think of a solution on O(N) complexity, i.e., in the order of 10^9. I'm not sure if it's optimal. We can generate the remaining prime numbers less than N (excluding the given primes) and try to form numbers less than N with these primes. Any hints on optimal approach? Last edit: 20221206 04:29:34 

smso:
20211028 08:25:06
Max value of composite from [13, 17, 19, 23, 29, 31, 37, 41, 43, 47] = 266186053068611 which overflows. 

yaseenmollik:
20200413 00:00:26
Solved it using InclusionExclusion Principle!!


nimphy:
20180429 05:36:07
@ mehmetin ，really？ 

chandan pandey:
20170703 20:52:46
Any approach other than Exclusion inclusion ?? 

Bhuvnesh Jain:
20161012 16:07:42
Why include "n = 0"? Easy one though. 

fR0DDY:
20160702 21:18:14
It was a silly integer overflow. :( Last edit: 20160703 03:31:14 

HM Mehrab:
20160418 08:43:04
There are others who have solved this problem, and well within the time limit I should add. So if your algorithm gets TLE, you should try to improve it. And there is no guarantee that all test cases are distinct. The worst case may appear many times in the test data. 

farhan764:
20160417 12:02:34
hey PS, my solution is giving all possible answer within .25 sec..........then why am i getting tle...can u plz check 

erlanggakm:
20160415 05:18:33
imho, case 2 : 2; its 25 and 49 since Almost Prime Numbers are not greater than N 
Added by:  HM Mehrab 
Date:  20160401 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 