What is the Fastest Method for Finding Prime Numbers and Combinations?

[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.

 

[mfb]

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.

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).

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.

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

 

[AlephZero]

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.

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!)

 

[Superposed_Cat]

Then the sieve is really bad apart from the first ~100 numbers (where you don't need it anyway).

How would you find the nth prime?

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

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

 

[mfb]

How would you find the nth prime?

Please don't remove relevant context in quotes:

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).

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.

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

There are 30! or roughly 2*10³² 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...

 

[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.

 

[CompuChip]

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

 

[mfb]

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?

 

[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.

 

[Borek]

There is an annual olympiad and there is always a question that has something to do with the 100000th prime number

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

 

[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.

 

[Vanadium 50]

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.

 

[mfb]

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.

 

[jim mcnamara]

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/

 

[kreil]

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

 

[Superposed_Cat]

Same. Nice profile pic kreil. Is that you?

 

[Zeda]

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.

30! = 2^15+7+3+13¹⁰⁺³⁺¹5⁶⁺¹7⁴11²13²17*19*23*29=2²⁶3¹⁴5⁷7⁴11²13²17*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, p^floor(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.

 

[kreil]

Same. Nice profile pic kreil. Is that you?

Nope, just a big Seinfeld fan