Semi-Primes

September 6, 2019

We have on several occasions seen functions for generating the primes less than n. Sometimes, what you want instead of primes are semi-primes, numbers which are the product of two primes. For instance, the six semi-primes less than 25 are 2×3=6, 2×5=10, 2×7=14, 3×5=15, 3×7=21 and 2×11=22.

Your task is to write a function that makes a list of the semi-primes less than n; use it to discover the number of semi-primes less than 10,000. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

3 Responses to “Semi-Primes”

  1. Paul said

    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

    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

    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);
        }
    }
    

Leave a Reply

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

WordPress.com Logo

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

Google photo

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

Twitter picture

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

Facebook photo

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

Connecting to %s

%d bloggers like this: