Algorithm
problem link- https://www.spoj.com/problems/KPRIMESB/
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<=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.
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
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI 3.14159265358979323846
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
const int MAXN = 1e6+5;
bool isPrime[MAXN];
void sieve(){
isPrime[0] = isPrime[1] = 1;
for(int i = 2;i*i <= 1000000; i++){
if(!isPrime[i]){
if(i*1LL*i <= 1000000){
for(int j = i*i;j <= 1000000; j += i)
isPrime[j] = 1;
}
}
}
}
int matrix[MAXN];
int primes[55], n, k;
void solve(){
for(int i = 0;i <= n; i++)
matrix[i] = 0;
for(int i = 0;i < k; i++){
int num = primes[i];
for(int j = num;j <= n; j += num){
matrix[j] = 1;
}
}
}
int main(){
sieve();
int tc = 1;
int t;
scanf("%d", &t);
while(t--){
scanf("%d%d", &n, &k);
for(int i = 0;i < k; i++)
scanf("%d", &primes[i]);
solve();
int ans = 0;
for(int i = 2;i <= n; i++){
if(!matrix[i] && isPrime[i]){
ans++;
}
}
printf("Case %d: %d\n", tc, ans);
tc++;
}
return 0;
}Input
1000 3
2 3 5
49 3
2 3 5
Output
Case 2: 1
Demonstration
SPOJ Solution-Almost Prime Numbers Again-Solution in C, C++, Java, Python