# Fastest prime number sieve

1. Nov 10, 2013

### Superposed_Cat

Hi, I was wondering what A)the fastest way to find primes is, the fastest I've found so far is the sieve of Eratosthenes.
B) The fastest way to find all possible combinations of a set are. e.g. cat-> act,cta,tca,atc,tac,cat
any help appreciated. thanks in advance.

Last edited: Nov 10, 2013
2. Nov 10, 2013

### Staff: Mentor

The fastest way to find n arbitrary primes? Then this sieve is not bad.
The fastest way to check if a number is prime? Then the sieve is really bad apart from the first ~100 numbers (where you don't need it anyway).

Use some systematic way to list all permutations. There are many algorithms to do that.

3. Nov 10, 2013

### AlephZero

Pick the first item at random. Then append the number of combinations of the smaller set that remains.

(Actually, this is a good computer programming exercise in writing recursive functions, and it's not quite as simple as it might seem!)

4. Nov 10, 2013

### Superposed_Cat

How would you find the nth prime?

I need one that could solve for all permutations for a 30 element set in under 3 hours.

5. Nov 10, 2013

### Staff: Mentor

Please don't remove relevant context in quotes:
To find the nth prime if n is not too large, I would first estimate its magnitude via the approximate prime density. Then use the sieve up to some number, afterwards I guess trial division is better due to its reduced memory requirements.

There are 30! or roughly 2*1032 of those permutations. Even if you can use every computer worldwide, there is no way to list or even store all those permutations within 3 hours.
Finding the next permutation is cheap in terms of CPU cycles, but the number of CPU cycles has some limit...

6. Nov 10, 2013

### Superposed_Cat

Oh.. last year in an Olympiad we were asked for the number of possible permutations of a 30 element set. We (it was a group thing) assumed that you would have to list the permutations first, I didn't think to just find the factorial. I feel so stupid now.

7. Nov 10, 2013

### CompuChip

Aww poor guys. You're still busy writing them out, I presume?

8. Nov 10, 2013

### Staff: Mentor

If you can convert the whole mass of earth to writing paper of 80g/m^2, you have 0.3mm^2 for each permutation or 0.01mm^2 per element. Letters with a size of 100µmx100µm are hard to read, but I guess that's not the most pressing issue then.

Where does the prime number question come from?

9. Nov 10, 2013

### Superposed_Cat

There is an annual olympiad and there is always a question that has something to do with the 100000th prime number or something and another about permutations, you have 3 hours to answer 10 questions. So you can see why I'm trying to find more efficient techniques. Each question has an integer answer and will take along time to work out if your code isn't efficient.

10. Nov 10, 2013

### Staff: Mentor

Chances are you don't have to know this number to answer the question.

11. Nov 11, 2013

### Superposed_Cat

ja, we thought too literal, now I know to think out of the box. the winning team only got 6/10 questions right and the people who worked for the place only got 7/10 right we got 4/10.

12. Nov 22, 2013

Staff Emeritus
30! = 265 252 859 812 191 058 636 308 480 000 000

By hand, this takes about 10 minutes to calculate. First get the number of zeroes at the end, and then get the rest. I found it convenient to do this in two pieces: take out the factors of 2, multiply the rest together, and then multiply this by all the factors of 2.

13. Nov 22, 2013

### Staff: Mentor

10 minutes sounds quick. Took me 6 minutes (that's what the watch says, didn't feel like that) to reduce it to 29 * 23 * 19 * 17 * 49 * 1001^2 * 2187^2 * 524288 * 10^7. After that, it is just stupid multiplication with big numbers, but with a group this is easy to parallelize.

14. Nov 22, 2013

### Staff: Mentor

The Miller-Rabin test for primality of a given tests for exactly what it says, but it is probabalistic.
http://en.wikipedia.org/wiki/Miller–Rabin_primality_test#Algorithm_and_running_time

Polynomial sieves: http://en.wikipedia.org/wiki/Quadratic_sieve are fast factorization algorithms, and are very fast for integers less than 100 decimal digits.

For finding the 100000th prime the Sieve of Eratosthenes is more than adequate. Just ran on under cygwin on an intel 2.8GHz dual-core. Got the answer in less than 8+ milliseconds. Actually it found the first 1,000,000 primes. But I did not feel like recoding it to make it stop at 100,000.

If this kind of number theory coding is interesting for you I would recommend Project Euler:
http://projecteuler.net/

15. Nov 25, 2013

### kreil

+1 for Project Euler, I'm a fan!

16. Nov 25, 2013

### Superposed_Cat

Same. Nice profile pic kreil. Is that you?

17. Nov 26, 2013

### Zeda

30! = 215+7+3+1310+3+156+17411213217*19*23*29=226314577411213217*19*23*29

Basically, for a given prime p<n, then at least floor(n/p) numbers are going to have p as a factor. Since they are multiplied, pfloor(n/p) is a factor. But then of those, an every p-th one of those numbers has an additional power of p. So essentially:
$\prod_{p}{p^{\sum_{k=1}^{\lfloor log_{p}(n)\rfloor}{\lfloor\frac{n}{p^{k}}}\rfloor}}$
Where p is over all primes. Alternatively, the sum can go from 1 to infinity and still be correct, but the value I provided is the last non-trivial value of the sum (the rest become 0).

Hopefully I got that all correct as I pulled it from my brain and that is known to not be so lucid at these hours :P

Depending on memory constraints and available math commands, you could determine the 100000th prime by keeping track of each new prime in an array and it's inverse in another array. Then you can multiply X (input) by each element in the inverse array up to the nth element, and once floor(sqrt(x))>array[n], increment n. You don't ever need to calculate sqrt(x), either ! Just use two counters C and D where D gets incremented by 2 every time C is reset to D.

18. Nov 26, 2013

### kreil

Nope, just a big Seinfeld fan