How many prime knots are there for crossing numbers greater than or equal to 17? I can't seem to find any useful resources indicating that they have been computed or that algorithms exists to compute the number of prime knots.
Number of prime knots for crossing number greater than 16
algorithmsknot-theory
Related Solutions
I expect there are more powerful tools available; but for a simple approach I would apply the Prime Number Theorem (PNT) and a sieve (as Yuval has already suggested).
One useful consequence of the PNT is that around a number N, approximately one out of every log(N) numbers is prime. (By 'log,' number theorists always mean the natural log 'ln'.) So around 2000, about 1 out of every 7.6 numbers is prime. Let's just look among the numbers 2001 to 2060 for our next prime-- I'm leaving extra space in case a big prime gap happens to show up around 2000.
Now we use the sieve-- we can throw out all even numbers in our list, since they are certainly not primes. Next, we can throw out everything divisible by 3, then everything divisible by 5, by 7, by 11,... When should we stop sieving? We can stop when we get to $\sqrt{2060} \approx 45$, since if any number in our list can be factored as M = ab, then one of the factors must be less than or equal to the square root of the biggest number in our list.
Of course, a computer would be happy to do this process for you. But, I just wrote down the list and went through my basic sieve (primes up to 43); and I got the prime numbers 2003, 2011, 2017, 2027, 2029, 2039, 2053.
Seeing the code would help to understand the points where it could be (or not) better than it is now, but initially there is a basic point you mention that could be enhanced, in your last step:
"So iterate from 1 to n, check if number has any prime factor less than Y, if yes, dont add it, otherwise add it."
- You would not need to start from $1$ but from $Y+1$, because a number under or equal to $Y$ has all the divisors under or equal to $Y$, so:$$n \ge Y+1$$(only the special case $n=1$ will be in your addition by default).So any $n \in [2,Y]$ can be discarded.
Now supposing that in a first step you sieved all the primes, then:
Now for the interval $[Y+1,Y^2]$ you would just need to add the prime numbers inside the interval that you already sieved, not the composite numbers. This is because any composite $n$ has at least a divisor under $\sqrt{n}$, so any composite number in the interval $[Y,Y^2]$ at least has a divisor in the interval $[2,Y]$. So if you had made in a first step the sieving of the primes, you will not need to verify again any number in $[Y,Y^2]$, just directly add the primes in that interval.
And finally you would need to test all composite numbers in the interval $[(Y+1)^2,X]$, because some of them could have all the divisors (except $1$) over $Y$, and in the other hand you can directly add all the primes in that interval.
I hope it helps, if you add the code I could have a look, just let me know in the comments. Probably is fine as it is, specially if the interviewer did not explain any details about how to make it better.
Best Answer
Using his program Regina, Benjamin Burton has computed the number of prime knots with 17, 18, and 19 crossings (see this link for reference). The table below summarizes the data from the link: