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 (i.e. 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
citizendot: 2022-12-06 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: 2022-12-06 04:29:34
smso: 2021-10-28 08:25:06

Max value of composite from [13, 17, 19, 23, 29, 31, 37, 41, 43, 47] = 266186053068611 which overflows.

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

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