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 ≤ 106) 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:
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!!
|
|
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 |
| Date: | 2016-04-01 |
| Time limit: | 0.5s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 GOSU JS-MONKEY |
RSS