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

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
-
What is the upper bound of n? Why limit it to languages you are familiar with? And just to be sure, this is not code golf, correct? – Steven Rumbalski Jan 23 '12 at 23:14
Upper limit atmost n=1000 – Arya Jan 24 '12 at 9:50
What is the objective winning criteria? – user unknown Jan 24 '12 at 15:11
-1 for no objective winning criteria and failure to clean up question when asked. – Steven Rumbalski Jan 24 '12 at 15:41
I may see an interesting approach to solving this with lazy evaluation, but I'm closing it until the deficiencies are corrected. – dmckee Jan 24 '12 at 16:53
show 1 more comment

closed as not a real question by dmckee♦Jan 24 '12 at 16:54

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, see the FAQ.

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
``````
-
 thank you very much – Arya Jan 24 '12 at 9:49

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
``````
-