Programming Praxis

4 Responses to “Semi-Primes”

1. Paul said

   September 6, 2019 at 1:06 PM

   In Python. The semiprimes are generated in order.

   from heapq import merge
   from itertools import takewhile
   
   def semiprimes(limit):
       prs = list(primes(limit // 2))
       seqs = [list(takewhile(lambda p: p <= limit, (a*b for b in prs[i+1:]))) for i, a in enumerate(prs)]
       return list(merge(*seqs))
   
   print(semiprimes(25))  # -> [6, 10, 14, 15, 21, 22]
   print(len(semiprimes(10**4)))  # -> 2600
   
2. Paul said

   September 8, 2019 at 7:40 AM

   An faster version in Python. The Python sort function is very efficient for a sequence of runs of already sorted items, so there is no point in using merge.

   def semiprimes4(limit):
       prs = list(primes(limit // 2))
       semis = []
       for i, a in enumerate(prs):
           if a * prs[i+1] > limit:  # saves  a lot of time
               break
           for b in prs[i+1:]:
               ab = a * b
               if ab > limit:
                   break
               semis.append(ab)
       return sorted(semis)
   
3. aman said

   September 19, 2019 at 10:33 AM

   bool isPrime(int n)
   {
   if (n <= 1)
   return false;

       for (int i = 2; i < n; i++)
           if (n % i == 0)
             return false;
   
       return true;
   }
   
   void SemiPrimes()
   {
       List<int> primeNos = new List<int>();
       List<int> semiPrimes = new List<int>();
       bool primeListFilled = false;
   
       for (int i=0;i<num;i++)
       {
           bool isprime = isPrime(i);
           if (i == num-1)
           {
               primeListFilled = true;
           }
           if (isprime)
           {
               primeNos.Add(i);
           }
           Debug.Log(" primeListFilled " + primeListFilled);
       }
       if (primeListFilled)
       {
         for(int i=0;i< primeNos.Count; i++)
         {
           Debug.Log("primeNos "+ primeNos[i]);
               for (int j = i+1; j < primeNos.Count; j++)
               {
                if (primeNos[i] * primeNos[j] < num)
                {
                 semiPrimes.Add(primeNos[i] * primeNos[j]);
                }
              }
         }
       }
   
       foreach (int n in semiPrimes)
       {
           Debug.Log(n);
       }
   }
   
4. matthew said

   October 7, 2019 at 7:03 PM

   Here’s some Haskell, making use of lazy lists:

   import Data.Lists
   
   primes = 2 : filter f [3,5..] where
     f n = all (\p -> n `mod` p /= 0) (takeWhile (\p -> p*p <= n) primes)
   
   semiprimes = products primes where
     products (p:q:ps) = p*q : merge (map (p*) ps) (products (q:ps))
   
   main = print $ take 100 semiprimes
   

   $ runghc semiprimes.hs 
   [6,10,14,15,21,22,26,33,34,35,38,39,46,51,55,57,58,62,65,69,74,77,82,85,86,87,91,93,94,95,106,111,115,118,119,122,123,129,133,134,141,142,143,145,146,155,158,159,161,166,177,178,183,185,187,194,201,202,203,205,206,209,213,214,215,217,218,219,221,226,235,237,247,249,253,254,259,262,265,267,274,278,287,291,295,298,299,301,302,303,305,309,314,319,321,323,326,327,329,334]
   

   All those merges build up in memory, but we can find eg. 5111663, the 1000000th semiprime without too much trouble in 30 seconds or so.

   If we include the squares of primes in the semiprimes, the code is even simpler:

   semiprimes = products primes where
     products (p:ps) = p*p : merge (map (p*) ps) (products ps)
   

   $ runghc semiprimes.hs 
   [4,6,9,10,14,15,21,22,25,26,33,34,35,38,39,46,49,51,55,57,58,62,65,69,74,77,82,85,86,87,91,93,94,95,106,111,115,118,119,121,122,123,129,133,134,141,142,143,145,146,155,158,159,161,166,169,177,178,183,185,187,194,201,202,203,205,206,209,213,214,215,217,218,219,221,226,235,237,247,249,253,254,259,262,265,267,274,278,287,289,291,295,298,299,301,302,303,305,309,314]
   

Leave a Reply

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out /  Change )

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

Notify me of new comments via email.

Notify me of new posts via email.

Δ