72 lines
2.5 KiB
Text
72 lines
2.5 KiB
Text
do -- Find Brilliant numbers - semi-primes whose two prime factors
|
|
-- have the same number of digits
|
|
|
|
local fmt = require( "fmt" ) -- RC Pluto formatting library
|
|
local int = require( "int" ) -- RC Pluto integer library, inc. prime utilities
|
|
|
|
-- returns a table of brilliant numbers to maxBrilliant
|
|
local function findBrialliant( maxBrilliant : number, ps : table ) : table
|
|
local bn <const>, maxPs <const> = {}, # ps
|
|
for n = 1, maxBrilliant do bn[ n ] = false end
|
|
|
|
-- brilliant numbers where one of the fators is 2
|
|
bn[ 4 ] = true
|
|
for p = 3, 7, 2 do bn[ 2 * p ] = true end
|
|
|
|
-- brilliant numbers where both factors are odd
|
|
local pStart, pEnd = 1, 9
|
|
while pStart < maxPs do
|
|
for p = pStart, pEnd, 2 do
|
|
if ps[ p ] then
|
|
bn[ p * p ] = true
|
|
for q = p + 2, pEnd, 2 do
|
|
if ps[ q ] then
|
|
bn[ p * q ] = true
|
|
end
|
|
end
|
|
end
|
|
end
|
|
pStart = pEnd + 2
|
|
pEnd = ( ( pStart - 1 ) * 10 ) - 1
|
|
if pEnd > maxPs then pEnd = maxPs end
|
|
end
|
|
return bn
|
|
end
|
|
|
|
do -- task
|
|
|
|
local maxPrime <const> = 1010 -- maximum prime we will consider, should be
|
|
-- enough to find the first brilliant number > 10^6
|
|
|
|
-- construct a sieve of brilliant numbers to maxPrime squared
|
|
-- using a sieve of primes to maxPrime
|
|
local brilliant <const> = findBrialliant( maxPrime * maxPrime
|
|
, int.arecomps( maxPrime ):map( | v | -> not v )
|
|
)
|
|
|
|
-- show the first 100 brilliant numbers
|
|
local bCount, n, p10 = 0, 0, 0
|
|
while bCount < 100 do
|
|
n += 1
|
|
if brilliant[ n ] then
|
|
fmt.write( "%6d", n )
|
|
bCount += 1
|
|
if bCount % 10 == 0 then print() end
|
|
end
|
|
end
|
|
|
|
-- show the first brilliant number >= 10^n, n = 1, 2, ..., 6
|
|
bCount, p10 = 0, 10
|
|
for bPos = 1, # brilliant do
|
|
if brilliant[ bPos ] then
|
|
bCount += 1
|
|
if bPos >= p10 then
|
|
fmt.write( "First brilliant number >= %8d: %8d", p10, bPos )
|
|
fmt.print( " at position %6d", bCount )
|
|
p10 *= 10
|
|
end
|
|
end
|
|
end
|
|
end
|
|
|
|
end
|