Suppose $A\subset[1,N]$ is a set of integers. If for any distinct $a,b\in A$ we have $(a,b)\leq M$ then how big can $|A|$ be? 


If $M=1$ then $|A|$ is at most $\pi(N)$ since the map $a\mapsto P\_+(a)$ (which sends $a$ to its largest prime factor) is an injection to the primes, and so the primes themselves are the most efficient. If $M=N$ then we can take $|A|=N$. What about $M$ in between? Can you beat the primes? It would be safe to assume that $A$ consists solely of $M$-smooth numbers since we can decompose $A=A\_1\cup A\_2$ where each $a\in A\_1$ is $M$-smooth and each $a\in A\_2$ has a prime factor which at least $M+1$. The large prime factors appearing as divisors in $A\_2$ cannot be repeated, so $|A\_2|\leq \pi(N)$. 



How big can a set of integers be if all pairs have small gcd?

> 
> We'll prove that the maximal cardinality of such a set for $M^2\leq N$ has size equal to $$\pi(N)+\sum\_{1<n\leq M} \pi(p(n))$$ where $p(n)$ is the smallest prime factor of $n$. Since $$\sum\_{1<n\leq M} \pi(p(n))\sim \frac{M^2}{2\log^2 M},$$ this proves that [Ilya Bogdanov's example of including all pairwise products of primes not exceeding $M$](https://mathoverflow.net/questions/221466/how-big-can-a-set-of-integers-be-if-all-pairs-have-small-gcd/221487?noredirect=1#comment546403_221466) is nearly optimal in terms of asymptotics.
> 
> 
> 


As you suggest in the question, this problem is equivalent to constructing the largest subset $A\subset S\_M(N)$ such that $\gcd(a,b)\leq M$ for every $a,b\in A$ where $S\_M(N)$ is the set of $n\leq N$ whose largest prime factor is at most $M$. 


To see why, suppose that $A$ satisfies $\gcd(a,b)\leq M$ for every $a,b\in A$. Then every prime that is greater than $M$ can divide at most one element of $A$. If $p>M$ divides $a\in A$, then making $a=p$ only helps create a larger set $A$. Since these primes do not interact with the $M$-smooth numbers, the proof is complete.


Let $T(N,M)$ denote the maximum size of such a set $A\subset S\_M(N)$. Then the size of the largest subset of $[1,N]$ with pairwise $\gcd$'s bounded by $M$ is $$\pi(N)-\pi(M)+T(N,M).$$ 


As mentioned by Fedja in the comments s, the reasoning above for the primes extends to all integers. By considering those primes $p,q\leq M$ such that $pq>M$, we see that there can only be exactly one such number divisible by $pq$. Similarly for any $p,q,r$ with $pq,qr,rp\leq M$ and $pqr>M$ there can only be one number in our set divisible by $pqr$. Thus we find that the maximal size is the sum over those integers whose largest proper divisor is less than $M$. Since the largest proper divisor of $n$ equals $n/p(n)$ where $p(n)$ is the least prime factor, we can group things based on this, and we have that $$T(N,M)=\sum\_{1<p\leq M}\sum\_{n\leq M:\ p(n)\geq p}1.$$ Rearranging this equals 
 $$\sum\_{1<n\leq M}\sum\_{p\leq p(n)}1=\sum\_{n\leq M}\pi\left(p(n)\right),$$ and for composite $n$ $p(n)\leq\sqrt{n}$, so the primes dominate this sum. Thus asymptotically we have $$T(N,M)\sim\sum\_{p\leq M}\pi(p)\sim\frac{M^{2}}{2\log^{2}M}.$$


