Differences between revisions 8 and 9
 ⇤ ← Revision 8 as of 2008-04-06 00:05:30 → Size: 2002 Editor: RogerHui Comment: ← Revision 9 as of 2008-12-08 10:45:48 → ⇥ Size: 1908 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 68: Line 68: [[BR]] <
> Line 71: Line 71: * [http://mathworld.wolfram.com/Semiprime.html MathWorld] * [http://www.en.wikipedia.org/wiki/Semiprime Wikipedia] * [http://www.research.att.com/~njas/sequences/A001358 On-line Encyclopedia of Integer Sequences A001358] * [http://www.research.att.com/~njas/sequences/A066265 On-line Encyclopedia of Integer Sequences A066265] * [[MathWorld:Semiprime|MathWorld]] * [[http://www.en.wikipedia.org/wiki/Semiprime|Wikipedia]] * [[OEIS:A001358|On-line Encyclopedia of Integer Sequences A001358]] * [[OEIS:A066265|On-line Encyclopedia of Integer Sequences A066265]] Line 76: Line 76: [[BR]] <
>

A semiprime is a number with exactly 2 (not necessarily distinct) prime factors. The semiprimes less than 50 are:

```   sp1=: (#~ 2 = #@q:) @ }. @ i.
sp1 50
4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49```

It is possible to produce this list without testing each integer i<n . A semiprime can be written as a product of primes p*q where p<:q .  p is necessarily less than %:n , and for each such p the possible primes q are those greater than or equal to p but less than n%p . For n=:50 , %:50 is 7.07 ; the primes less than 7.07 are 2 3 5 7 ;  and

```   50 % 2 3 5 7
25 16.6667 10 7.14286
/:~ (2 * 2 3 5 7 11 13 17 19 23), (3 * 3 5 7 11 13), (5 * 5 7), 7*7
4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49```

In general,

```nplt=: p:^:_1        NB. #primes <  n
plt =: i.&.(p:^:_1)  NB.  primes <  n

sp  =: 3 : '/:~ ; (* nplt }. plt@(y&%))&.> plt %:y'

*./ (sp1 -: sp)"0 >: i.1000
1```

The number of semiprimes less than n derives from the same reasoning:

```nsp=: 3 : '+/ (nplt@(y&%) - nplt) plt %:y' " 0

nsp 50
17
*./ (nsp -: #@sp)"0 >: i.1000
1
nsp 10^i.10
0 3 34 299 2625 23378 210035 1904324 17427258 160788536```

## Collected Definitions

```sp1 =: (#~ 2 = #@q:) @ }. @ i.

nplt=: p:^:_1        NB. #primes <  n
plt =: i.&.(p:^:_1)  NB.  primes <  n

sp  =: 3 : '/:~ ; (* nplt }. plt@(y&%))&.> plt %:y'

nsp =: 3 : '+/ (nplt@(y&%) - nplt) plt %:y' " 0```