Essays/Semiprimes
< Essays
Jump to navigation
Jump to search
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
There is an alternative formulation which works with a list q of primes less than n%2 and a list p of primes <: %:n .
sp2=: 3 : 0 q=. i.&.(_1&p:) -:>:y p=. q {.~ q I. %:y /:~ ; p *&.> (i.#p) }.&.> (q I. >.y%p) {.&.> <q ) *./ (sp2 -: sp1)"0 i.1000 1
The Number of Semiprimes
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' sp2 =: 3 : 0 q=. i.&.(_1&p:) -:>:y p=. q {.~ q I. %:y /:~ ; p *&.> (i.#p) }.&.> (q I. >.y%p) {.&.> <q ) nsp =: 3 : '+/ (nplt@(y&%) - nplt) plt %:y' " 0
See also
- MathWorld
- Wikipedia
- On-line Encyclopedia of Integer Sequences A001358
- On-line Encyclopedia of Integer Sequences A066265
Contributed by Roger Hui.