Semiprime

Author

Eric W. Weisstein
July 28, 2022

This notebook downloaded from http://mathworld.wolfram.com/notebooks/PrimeNumbers/Semiprime.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Semiprime.html.

©2022 Wolfram Research, Inc. except for portions noted otherwise

Code

LPF[n_]:={#,Length[IntegerDigits[#]]&/@Prepend[#,n]}&[Power@@@FactorInteger[n]]

SemiprimeQ[1]:=False
SemiprimeQ[n_Integer]:=Plus@@(Last/@FactorInteger[n])==2

SemiprimePi[n_] := Total[PrimePi[n/Prime[#]] -# + 1&/@Range[PrimePi[Sqrt[n]]]]

Semiprimes

Select[Range[50],SemiprimeQ]

Squarefree

Position[FactorInteger[Range[50]],{{p_,1},{q_,1}}]//Flatten

SemiprimePi

Check

With[{n=10^4},
Rest[FoldList[Plus,0,Boole[SemiprimeQ[#]]&/@Range[n]]]==SemiprimePi/@Range[n]
]//Timing

Powers of 10

Length[l=Select[Range[10^6],SemiprimeQ]]//Timing

Table[Count[l,_?(#<10^n&)],{n,0,6}]

SemiprimePi/@(10^Range[0,6]-1)//Timing

Identities

(EulerPhi[p q])==(p-1) (q-1)

FunctionExpand[EulerPhi[p q],p≠q&&(p|q)∈Primes]

Factor[p q-(p+q)+1]

Semiprimes with two large prime factors

LPF[38!+1]//Timing

LPF[10^48+19]//Timing

LPF[10^50+27]//Timing

LPF[10^54-3]//Timing

LPF[10^53+63]//Timing

LPF[10^55-9]//Timing

LPF[10^63+19]//Timing

Mersenne number semiprimes

A085724

Cases[Import["http://oeis.org/A046051/b046051.txt","Table"],{n_,2}:>n]

1427 and 1487 are also terms. 1277 is the only remaining unknown below them. - Charles R Greathouse IV, Jun 05 2013

Algorithm

Careful: FactorInteger[n, 2] returns two factors that are not necessarily prime

200

Position[Table[Total[Last/@FactorInteger[2^n-1,3]],{n,200}],2]//Flatten//Timing

Position[Table[Total[FactorInteger[2^n-1,3][[All,-1]]],{n,200}],2]//Flatten//Timing

Position[PrimeOmega[2^Range[200]-1],2]//Flatten//Timing

250

Select[Range[250],Total[Last/@FactorInteger[2^#-1,3]]==2&]//Timing

Position[Table[Total[Last/@FactorInteger[2^n-1,3]],{n,250}],2]//Flatten//Timing

Position[PrimeOmega[2^Range[250]-1],2]//Flatten//Timing

300

Select[Range[300],Total[Last/@FactorInteger[2^#-1,3]]==2&]//Timing

...ran overnight...

$Version