javadata-structuresprimes

Iterating over a data structure with 51 million primes quickly

What's the best data structure (in java) for the task of loading 51 million primes and then iterating over them?

I need to know, for example, the primes that are between 1000000000 and that same number minus 100000.

Solution

  • A binary search isn't going to be wonderful for this data, since the first half of the primes are going to be closer to each other than the last half of them.

    You might be able to improve on your search by knowing how many primes there are under x. Maybe skew the cut by using the approximation mentioned in the link.

    My first try would be this. I'd have two arrays.

    1. An array of all the primes.
    2. An array that tells me where in the first array the first prime above 1000*n was. So if I wanted to find the first prime with a value of 5000 or more, I'd look at secondArray[5000/1000-1].

    I'd get a rough position with array 2 before doing anything with array 1.