Quase_primo.cpp

#include <bits/stdc++.h>
#define K 45
using namespace std;

typedef long long int ll;

int n, k, p[K], soma;

inline void f(int i, ll mult, int qnt) 			//indice atual, valor atual, quantidade de fatores na multiplicacao
{
	if(mult > n) return; 				//se o valor ultrapassou n, eu retorno
	
	if(i == k) 					// se ja passei por todos os indices
	{
		if(mult == 1 or qnt == 0) return; 	//casos invalidos
		if(qnt%2) soma += (n/mult); 		//se a quantidade for impar, eu somo o conjunto na minha soma
		else soma -= (n/mult);			//do contrário, eu subtraio
		return;
	}
	
	f(i+1, mult, qnt);				//chamo a funcao sem colocar o valor do indice
	f(i+1, mult*p[i], qnt+1);			//e colocando o valor do indice
}

int main()
{
	scanf("%d %d", &n, &k);
	for(int i = 0 ; i < k ; i++)
	{
		scanf("%d", &p[i]);
	}
	soma = 0;
	f(0, 1, 0);					//adiciona na soma a quantidade total de divisores menores que n desses primos
	printf("%d\n", n-soma);				//logo, basta subtrairmos isso da quantidade total de valores
}