0

What could be a better, more efficient way to find if a given set of numbers have at least one prime number in it? We can test each number one by one, but could there be a better, more optimized solution?

jadebit
  • 1
  • 2
    What is the range of the numbers? – AakashM Mar 09 '22 at 11:17
  • @AakashM **No negatives**, so that essentially means a range of 0 to N. The goal is to find if there is even one prime number in the set or not. – jadebit Mar 09 '22 at 11:19
  • So these are unconstrained `BigNumber`s of some kind? Or 32-bit integers? Or? – AakashM Mar 09 '22 at 11:37
  • 1
    @AakashM Yes, 32-bit integers – jadebit Mar 09 '22 at 11:46
  • There are too man primes in 32-bit for any clever fast prime-check. So I think in worst case you must check them all. – MrSmith42 Mar 09 '22 at 12:41
  • @MrSmith42 **Okay, say we have to do the same for numbers up to 10,000.** Can there be any way other than checking the primality of all the numbers until a prime is found? – jadebit Mar 09 '22 at 12:46
  • @jadebit: Of cause you need to look at all numbers (in worst case). So you cannot get better than `O(n)`. The question is what do you need to do with them. If they are <=10000 you can simply look them up in a Set of all primes <=10000 (takes `O(1)`. => Total of `O(n)`. – MrSmith42 Mar 09 '22 at 14:46
  • 2
    It all depends on what the set looks like. Random numbers? Test them one by one. A bunch of numbers out of a specific range of large numbers? Run a prime sieve for that range. etc – btilly Mar 09 '22 at 15:22
  • For number ranges like `all integers from 1 to N`, the fastest algorithms are called "Sieves". Variations of the [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) are the most common, and there are many examples available (I have several [myself](https://stackoverflow.com/a/1134851/109122)). – RBarryYoung Mar 09 '22 at 16:49
  • 3
    There are deterministic versions of the Miller-Rabin test for 32-bit integers that are faster than doing trial division, especially for values near the upper bound. Also there are 6542 primes less than 2^16, so you can precompute these into a set to be used for checking the primality of values in your set < 2^16. – President James K. Polk Mar 09 '22 at 16:51
  • What’s your approach? – Muhammad Mohsin Khan Mar 10 '22 at 17:46

1 Answers1

0

IIRC there are ~700MByte of 32bit primes m= ~700M / 4 and if you do 32bit SoE its only 512MByte so if you have enough memory you can:

  1. find max of your array O(n)

  2. use SoE to get all primes up to max

    This might be pre-computed and stored in file, You can either store list of primes of SoE map. List of primes files are downloadable online in binary form (fast to load)

  3. check each number if it is present in primes

    this is O(n*log(m)) if list of primes or O(n) if SoE map

If memory is a problem then:

  1. sort your numbers ascending ~O(n.log(n))

  2. do incremental primes search ~O(m^2)?

    where m is max of your array

  3. for each found prime check if it is present in array (incrementaly) ~O(1)

Also see this for some additional ideas:

You can also combine SoE with the division just like I did in the int isprime(int p) in previous link. I have 8 smaller periodic SoE maps primes_map[] for first primes to hugely speed up the division ignoring majority of non primes with single division (aligning to SoE map period).

Spektre
  • 49,595
  • 11
  • 110
  • 380