Numbers that are divisible by at least three different primes [closed]

Question

I was studying different sequences related to prime numbers and came across this sequence:

A000977: Numbers that are divisible by at least three different primes.

Write code to find the n-th number in this sequence in C, C++ or Python. (I am familiar with these languages only.)

For example:

• 1st number = 30
• 2nd number = 42

Answer 1

This list (numbers divisible by at least three primes) can be computed efficiently using the Sieve of Eratosthenes, but instead of "striking out" a number for being divisible by a prime, we increment a counter.

# Generate a list of numbers divisible by at least three different primes.
def divisible_by_three_primes():
    # This function generates an infinite list by rebuilding the sieve as
    # needed.  last_result is used to avoid yielding values from previous
    # sieves.
    sieve_size = 100
    last_result = 0

    while True:
        # strikes[idx] counts how many prime numbers are divisible by idx
        strikes = [0] * sieve_size

        for i in range(2, sieve_size):
            if strikes[i] == 0:
                # i is a prime number
                for j in range(i * 2, sieve_size, i):
                    strikes[j] = strikes[j] + 1
            elif strikes[i] >= 3:
                # i is divisible by at least 3 different primes
                if i > last_result:
                    last_result = i
                    yield i

        sieve_size = sieve_size * 2

n = input()

for i, x in enumerate(divisible_by_three_primes(), 1):
    if i == n:
        print x
        break

Answer 2

Python, 101 chars

N=input()
i=1
while N:i+=1;N-=sum(i%j==0for j in range(2,i)if all(j%k for k in range(2,j)))>2
print i

example:

$ echo 17 | ./threeprimes.py 
138