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
|
codepheonix:
2025-09-12 14:59:16
<snip>
|
|
rising_stark:
2024-11-18 18:36:40
@citizendot
|
|
rising_stark:
2024-11-18 18:35:14
n =0, costed me 1 WA |
|
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 |
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 |