Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fastest prime number sieve

  1. Nov 10, 2013 #1
    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. jcsd
  3. Nov 10, 2013 #2

    mfb

    User Avatar
    2016 Award

    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.
     
  4. Nov 10, 2013 #3

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    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!)
     
  5. Nov 10, 2013 #4
    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.
     
  6. Nov 10, 2013 #5

    mfb

    User Avatar
    2016 Award

    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...
     
  7. Nov 10, 2013 #6
    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.
     
  8. Nov 10, 2013 #7

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    Aww poor guys. You're still busy writing them out, I presume?
     
  9. Nov 10, 2013 #8

    mfb

    User Avatar
    2016 Award

    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?
     
  10. Nov 10, 2013 #9
    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.
     
  11. Nov 10, 2013 #10

    Borek

    User Avatar

    Staff: Mentor

    Chances are you don't have to know this number to answer the question.
     
  12. Nov 11, 2013 #11
    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.
     
  13. Nov 22, 2013 #12

    Vanadium 50

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    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.
     
  14. Nov 22, 2013 #13

    mfb

    User Avatar
    2016 Award

    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.
     
  15. Nov 22, 2013 #14

    jim mcnamara

    User Avatar

    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/
     
  16. Nov 25, 2013 #15

    kreil

    User Avatar
    Gold Member

    +1 for Project Euler, I'm a fan!
     
  17. Nov 25, 2013 #16
    Same. Nice profile pic kreil. Is that you?
     
  18. Nov 26, 2013 #17
    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:
    [itex]
    \prod_{p}{p^{\sum_{k=1}^{\lfloor log_{p}(n)\rfloor}{\lfloor\frac{n}{p^{k}}}\rfloor}}[/itex]
    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.
     
  19. Nov 26, 2013 #18

    kreil

    User Avatar
    Gold Member

    Nope, just a big Seinfeld fan
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Fastest prime number sieve
  1. Prime number test (Replies: 4)

  2. Prime number code, C++ (Replies: 16)

Loading...