KPRIMES - Almost Prime Numbers
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.
Input
First line of input consists of an integer T (1<=T<=100), denoting the number of test cases. Then T test cases follow. Each case begins with a line containing two integers N (0<=N<=10^4) and K (1<=K<=5). 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
HM Mehrab:
2016-04-01 12:29:48
Here you go. The tougher version: http://www.spoj.com/problems/KPRIMESB/ |
|
mehmetin:
2016-03-28 12:51:09
psetter should move this problem to tutorial and prepare another version with higher constraints. N<=10^9, K<=1000 seems fine. Last edit: 2016-03-28 13:49:47 |
|
Scape:
2016-03-27 22:23:03
This is too easy, should be moved to tutorial. Why not N <= 10^9, K <= 1000? |
|
farhan764:
2016-03-27 13:17:49
using sieve algo it can be solve easily....... |
|
lalit_nit:
2016-03-27 12:52:22
Reduce time limit...Accepted through bruteforce too.... |
|
HM Mehrab:
2016-03-27 06:39:32
The original problem was written with tougher constraints. But then the constraints were made easier for the 1st round of the contest. A tougher constraints version will appear in a future round of the contest. Last edit: 2016-03-27 09:47:27 |
|
mehmetin:
2016-03-26 10:08:52
Nice problem, but the constraints are too low. Could be at least something like T = 1000, N <= 10^6, K <= 10. Last edit: 2016-03-26 11:11:07 |
Added by: | imranziad |
Date: | 2016-03-23 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |
Resource: | IAPC Round #1 - H.M. Mehrab |