Quickly telling if a number can be represented as the multiple of two primes?-CodePudding

Let's say you have 10e4 numbers. Each number doesn't exceed 10e6. How can you efficiently check for each number if it can be represented as the multiple of two primes?

Examples: 15 can be represented as 3 * 5. 6 can be represented as 2 * 3. But 8 can't be represented by two primes.

CodePudding user response：

If you do not need to know the primes just if it is possible:

You could precalculate a boolean table with 10e6 entries which represents if the number can be represented as the multiple of two primes.

Than you can lookup every number in O(1).

Creating the table would take some time, but can be done upfront.

CodePudding user response：

You can precalculate a all prime numbers up to 5e6 (list_of_primes) and check for each number n with the following algorithm:

for prime in list_of_primes:
   x = n / prime
   
   if (x is in list_of_primes) and (x != prime) and (x*prime==n):
      return True

return False

This algorithm is not optimised, but with your dimensions should work fine. Also I hope that the Pseudo-Code is some what understandable.

Edit: The calculation of the list of primes can be done with the Sieve of Eratosthenes.

CodePudding user response：

Try division of all primes up to about 1000 (make a list of these).

CodePudding user response：

(Assuming numbers of the form x*x, where x is prime, are ok)

I'll call valid a number that can be represented as the product of 2 primes. If a number x is valid, there is only one representation as the product of 2 primes a and b. In fact, the only divisors of x are 1, a, b and x.

Thus an algorithm to check if a number x is valid, is to take each primes a less or equal than sqrt(x), and see if a divide x. If so, check if b = x/a is also a prime. If that's the case, x is valid, else x is not valid. Memoizing the list of primes can really speedup the process.

check_2_primes_representation(X):
    index = 0
    prime = list_of_prime[index]
    while(prime < sqrt(X))
        if(x mod prime == 0): # prime is a divisor of x
            return is_prime(x/prime)
        index  = 1
        prime = list-of_prime[index]
    return false

Another way to look at this problem is to generate the list of all valid numbers. This is quite easy to do, as you just need to multiply primes together. A few tricks can gain quite a bit of time : you only need a number once, so we only do products of the form a*b, where a <= b. We can thus stop when a > sqrt(10e6).

valid_numbers:
   list = []
   for a in list_of_primes:
       if a > sqrt(10e6):
           break #leave outer loop
       for b in primes_greater_than(a):
           if a*b > 10e6:
               break #leave inner loop
           list.push(a*b)
    return list

I went fast on some points, feel free to ask for an detailled explanation.

CodePudding user response：

There are just 168 prime numbers under 1000 = sqrt(10^6), and about 78,000 under 10^6. If your number is the product of two primes, the smaller one has to be one of the 168 under 1000.

Let's say big N is the max input and little n is the specific input. Here N = 10^6.

Store all primes <= N in a map. Given n, for prime p <= sqrt(n), check if n%p == 0. If so, check if n/p is in the map. Return true if it is, false otherwise.

Complexity:

Given a max value N, and a particular n <= N to check, this is O(sqrt(n)) time, and O(N / ln(N)) space. The space complexity comes from the number of primes <= N, which by the prime number theorem is appx. N / ln(N).