16
$\begingroup$

The high school textbook I am using has the example of semi-prime numbers. They wanted students to find (by "perspiration") all the semi-prime numbers less than $50$ (for a question on set theory).

A semi-prime number is the product of exactly two prime numbers (not necessarily distinct).

How would I generate the first $n$ semi-prime numbers using Mathematica?

$\endgroup$
  • $\begingroup$ Closely related: Generating a list of cubefree numbers $\endgroup$ – Artes Jan 28 '14 at 13:11
  • $\begingroup$ As always, the help of this community is very much appreciated! Thank you to everyone who responded. $\endgroup$ – Tom De Vries Jan 29 '14 at 13:18
16
$\begingroup$

You could use FactorInteger to find out whether or not there are exactly two primes building up a number:

SemiPrimeQ[n_Integer] := With[{factors = FactorInteger[n]},
  Total[factors[[All, 2]]] == 2
  ]

The rest is easy:

Select[Range[50], SemiPrimeQ]
(* {4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49} *)

And for those who like inline anonymous functions

Select[Range[50], Total[Last /@ FactorInteger[#]] == 2 &]
(* {4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49} *)

Update

If you want to create all semi primes which consist of primes smaller than the n-th prime, then this is a one-liner too. Here are all semi primes for the first 10 prime numbers:

Union[Times @@@ Tuples[Array[Prime, 10], 2]]
(* {4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, \
46, 49, 51, 55, 57, 58, 65, 69, 77, 85, 87, 91, 95, 115, 119, 121, \
133, 143, 145, 161, 169, 187, 203, 209, 221, 247, 253, 289, 299, 319, \
323, 361, 377, 391, 437, 493, 529, 551, 667, 841} *)
$\endgroup$
  • $\begingroup$ Wow, that was fast, and I appreciate that answer. Makes sense to me! I was messing around with lists of Primes and Tuples. This does just what I wanted, THANK YOU, I'll just wait a bit and see if there are other answers. $\endgroup$ – Tom De Vries Jan 27 '14 at 16:26
  • $\begingroup$ @TomDeVries, yes, waiting is always good, because people tend to look on unaccepted question to gain reputation. Many surprising answer can come up this way and you will see many different approaches. $\endgroup$ – halirutan Jan 27 '14 at 16:31
  • $\begingroup$ @RunnyKine In fact... let me check. $\endgroup$ – halirutan Jan 27 '14 at 16:45
  • $\begingroup$ @RunnyKine You have to check further ;-) The problem is that the last list is (due to Tuples) not sorted. $\endgroup$ – halirutan Jan 27 '14 at 16:48
  • $\begingroup$ Ah, you're right. My mistake. $\endgroup$ – RunnyKine Jan 27 '14 at 16:50
20
$\begingroup$

The built-in functionPrimeOmega gives you the number of prime factors and counts multiplicities. Therefore, this can easily be used to give you semi-primes as you have defined them:

With[{r = Range[50]}, Pick[r, PrimeOmega[r], 2]]
$\endgroup$
  • 1
    $\begingroup$ Thanks for that, no idea about that function $\endgroup$ – Tom De Vries Jan 27 '14 at 16:50
  • 2
    $\begingroup$ Never mistake PrimeOmega with OmegaPrime! +1 $\endgroup$ – halirutan Jan 29 '14 at 17:10
  • 1
    $\begingroup$ @halirutan "Semi-Primes Assemble!" $\endgroup$ – KennyColnago Jan 31 '14 at 17:14
8
$\begingroup$

By using a pregenerated list of prime numbers:

lst = Prime[Range@PrimePi[25]];
Select[Union@Flatten[lst*# & /@ lst], # < 50 &]
(* {4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49} *)
$\endgroup$
1
$\begingroup$

For fun, here's an approach that uses ReplaceList:

With[{n = 50}, 
 Union @@ ReplaceList[
   Array[Prime, n], {pre___, y_, rest___} :> y {pre, y}]]

(* {4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, \
55, 57, 58, 65, 69, 77, 85, 87, 91, 95, 115, 119, 121, 133, 143, 145, \
161, 169, 187, 203, 209, 221, 247, 253, 289, 299, 319, 323, 361, 377, \
391, 437, 493, 529, 551, 667, 841} *)
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.