I think this can be done in a straight-forward brute force manner. Consider the first 7 primes [2,3,5,7,11,13,17]. Each of these primes defines a "sieves", tha

I think this can be done in a straight-forward brute force manner. Consider the first 7 primes [2,3,5,7,11,13,17]. Each of these primes defines a "sieves", that can be used to filter out multiples of it. For instance, 2 defines the sieve [0,2,4,6,...] while 17 defines the sieve [0,17,34,...]. Instead of infinite sieves, consider only the finite sieves that go up to 100. for instance, 17 would give the sieve [0,17,34,...,85]. Over any interval of 100 integers, all multiples of p can be filtered out by filtering out the contents of p's finite sieve with some constant offset (<p). For instance, on the interval [0,100), we can filter out all multiples of 3 by filtering out the sieve [0,3,6,...,99]. Similarly, on the interval [10,110), we can filter out the multiples of 3 using the sieve [2,5,8,...98]. The notation here is a bit backward, but makes sense if you think of the sieve as a bit-field with 100 elements labeled 0 to 99. The sieve [2,5,8,...98] then represents the bitfield where every third element is true, starting with the second element. As a notional shorthand, we can represent this sieve as [3]+2, to represent all multiples of 3, with an offset of 2 (within the range [0,100). Formally speaking: [p]+k = [p * n + k | for integers n,k where 0 <= p * n + k < 100] For sieves X,Y define X | Y to be the union of X and Y. Under the bitfield interpenetration, a bit in X | Y is set if it is set in either X or Y. For every range of 100 integers, there exists a sieve that filters out all multiples of both p and q. This sieve takes the form: [p] + k | [q] + m. We can further restrict 0<=k<p and 0<=m<q. Note that there are only finitely many such sieves. Over any sequence of 100 integers, one of those finitely many sieves will filter out all multiples of p and q. This approach can be extend to any number of primes. Construct all such sieves for the primes [2,3,5,7,11,13,17]. For each sieve, count how many elements it allows through, and find the sieve which allows the fewest elements through. This is an upper bound of the number of integers within a range of 100 that are not a multiple of the first 7 primes. Assuming your range of integers starts at at least 18, this is an upper bound on the number of primes it can have. In python: primes=[2,3,5,7,11,13,17] sieves=[set()] for p in primes: newSieves=[] for k in range(0,p): toAppend = set([ k + pp for pp in range(0,100,p) if k + pp <= 100]) for sieve in sieves: newSieves.append(sieve | toAppend) sieves = newSieves print "\n{}:".format(p) print 100-min([len(s) for s in sieves])