KPRIMESB - Almost Prime Numbers Again

no tags 

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 (ie. composite numbers not divisible by any of the given K prime numbers) that are not greater than N.


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.


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.


1000 3
2 3 5
49 3
2 3 5
Case 1: 100
Case 2: 1

hide comments
yaseenmollik: 2020-04-13 00:00:26

Solved it using Inclusion-Exclusion Principle!!
Take care of corner cases like n = 0 or 1.

Last edit: 2020-04-13 00:01:09
nimphy: 2018-04-29 05:36:07

@ mehmetin ,really?

chandan pandey: 2017-07-03 20:52:46

Any approach other than Exclusion inclusion ??

Bhuvnesh Jain: 2016-10-12 16:07:42

Why include "n = 0"? Easy one though.

fR0DDY: 2016-07-02 21:18:14

It was a silly integer overflow. :(

Last edit: 2016-07-03 03:31:14
HM Mehrab: 2016-04-18 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: 2016-04-17 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: 2016-04-15 05:18:33

imho, case 2 : 2; its 25 and 49 since Almost Prime Numbers are not greater than N

HM Mehrab: 2016-04-01 19:16:31

I can't come up with an efficient solution to those constraints. If you want those constraints, you'll have to make the problem yourself lol

Last edit: 2016-04-01 21:50:28
mehmetin: 2016-04-01 18:42:56

A still harder version is possible (for example N<=10^9, K<=1000, T and time limit can be chosen accordingly)

Added by:HM Mehrab
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY