1

I need to find a certain amount of prime numbers in ascending order, starting from 2. I have a working algorithm which takes a number-limit as a parameter - it finds all primes that are less than the limit.

For example - for param 20 it would return 2,3,5,7,11,13,17,19, but I need to input 5 and get 2,3,5,7,11. What is the best way? I am using the Sieve of Eratosthenes and there is no way to limit the number-deleting part, since I don't know how big the 195th prime number is and I therefore don't know if I should delete all multiples of 2 up to 1568 or 1268426. I hope the question is clear, thanks for help

Improve this question
4
  • 1
    Can you provide your code or at least some pseudo-code? Commented Jan 29, 2012 at 20:21
  • 1
    See also: projecteuler.net/problem=7 - if you solve it, you will get access to some useful resources. Commented Jan 29, 2012 at 20:23
  • @KorhanÖztürk nope, it's a part of a older competition in programming, specifically in algorithms and this was bugging me off Commented Jan 29, 2012 at 20:32
  • I see.. So, did the algorithm below worked for you? @Magicmaster Commented Jan 29, 2012 at 21:08

3 Answers 3

Reset to default
5

There are several ways to do what you want.

The prime number theorem says that the number of primes less than n is asymptotically equal to n/log(n). You could add a small buffer, then do the Sieve of Eratosthenes, and throw out any primes beyond your limit.

Rather than an approximation, there are formulas that compute the exact number of primes less than n without listing the primes. You could use one of those formulas to find the n th prime, then use a Sieve to make the list of primes. Google for "Legendre sum" and "Lehmer's formula" if you want to take this approach.

You could use a segmented Sieve of Eratosthenes. Sieve up to some convenient limit. If you've got the answer, stop. Otherwise, pick the next segment, and then the next, and so on until you've found the number of primes that you want.

There is a very clever method of generating an infinite list of primes that replaces the bit-array of the Sieve of Eratosthenes with a priority queue. Google for Melissa O'Neill's paper The Genuine Sieve of Eratosthenes.

You can see complete explanations and implementations of all of these algorithms here.

By the way, the 195th prime is 1187. There are 247 primes less than 1568, and 97790 primes less than 1268426.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

The best options are, in my opinion, the segmented sieve and a monolithic sieve with upper bound derived from the prime number theorem plus a small buffer. The priority queue method is slow.
Agreed. There is actually an exact formula for the upper bound of the number of primes not exceeding n, which you can look up in any number theory textbook. But it misses the mark by quite a bit, and you're probably better off with the n / log(n) approximation. PS to Fischer: thanks for the edit.
0

Sometime ago, I wrote a small module that deals with prime numbers (which served my needs when working on Project Euler stuff). This is decently quick in that it keeps track of a list of prime numbers it has seen. This greatly reduces the computation time.

This is the major routine you will need (written in python). The documentation is mediocre, but I hope this helps.

def primes(num, l=[]):

    # l is the list of prime numbers you already have
    # This is reused to check for primality of a number

    if len(l) == 0: l = get_list() # Read from disk

    # Check to see if a sublist can be created
    e = l[-1]
    if (num < e):
        res = search.binary_low(l, num)
        return l[:res[0]+1]

    e = 6*(ceil(e/6))

    lim = num + 1
    # Extend the current list
    for n in range(e, lim, 6):
        m = n - 1
        if isprime(m, l): l.append(m)
        m = n + 1
        if isprime(m, l): l.append(m)

    # Save to pickle
    set_list(l) # Write to disk

    return l

You can find related routines over here

https://github.com/pavanky/expo/blob/master/python/prime.py

https://github.com/pavanky/expo/blob/master/python/search.py

Improve this answer

Comments

0

You can take the same idea behind the original Sieve of Eratosthenes, but do it iteratively. 

find_n_primes(num_primes):
  primes = [2]
  i = 3
  while primes.size < num_primes:
    is_prime = true
    for p in primes:
      if p > sqrt(i):
         break
      if i % p == 0: 
        is_prime = false
        break
    if is_prime:
      primes.add(i)

    i++
  return primes

Basically, rather than taking multiples of each number up to a fixed point, iterate through n, and check all primes you've already found, instead.

Improve this answer

5 Comments

This seems right, but assuming I have an array of numbers from which I delete non-primes, I don't know how big the array should be and how great numbers should I delete
[Comment explaining my downvote.] This works, but will be very slow; it's quadratic in the size of the num_primes'th prime. You will see that if you try to find the millionth prime. And the algorithm is trial division, not the Sieve of Eratosthenes. See my answer for several better solutions.
@Magicmaster you don't. You build a vector / list / whatever of primes as you go. You're not deleting from a list, you're adding to a vector.
@user448810 That doesn't make it an invalid (except my description). Based on his description, it doesn't sound like he's going after the millionth prime, and thus probably doesn't need something super optimal. Additionally, you are doing at max sqrt(n) divisions per number, so you're < n^2, and with some minor optimizations, it was enough to solve a large portion of projecteuler.
I see. I don't think that this has much to do with the sieve, as the point of it is to have an array of numbers and remove multiples of each prime, not checking whether a number is a prime. But this should suffice, as I will need primes only up to thousands

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.