N-smooth numbers: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
(36 intermediate revisions by 15 users not shown) | |||
Line 3:
'''n-smooth''' numbers are positive integers which have no prime factors <big> > </big> '''n'''.
The '''n'''
<br>there are <u>no</u> '''9-smooth''' numbers.
Line 10:
<br>2-smooth numbers are non-negative powers of two.
<br>5-smooth numbers are also called
<br>7-smooth numbers are also called
Line 23:
;Task:
:* calculate and show the first '''25''' n-smooth numbers for '''n=2''' ───► '''n=29'''
:* calculate and show three numbers starting with '''3,000''' n-smooth numbers for '''n=3''' ───► '''n=29'''
:* calculate and show twenty numbers starting with '''30,000''' n-smooth numbers for '''n=503''' ───► '''n=521''' (optional)
Line 42:
:* Wikipedia entry: [[wp:Hamming numbers|Hamming numbers]] (this link is re-directed to '''Regular number''').
:* Wikipedia entry: [[wp:Smooth number|Smooth number]]
:* OEIS entry:
:* OEIS entry:
:*
:* OEIS entry:
:* OEIS entry:
:* OEIS entry:
:* OEIS entry:
:* OEIS entry:
:* OEIS entry:
:* OEIS entry: [[oeis:A080683|A080683 23-smooth numbers]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">V primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]
F isPrime(n)
I n < 2
R 0B
L(i) :primes
I n == i
R 1B
I n % i == 0
R 0B
I i * i > n
R 1B
print(‘Oops, ’n‘ is too large’)
R 0B
F init()
V s = 24
L s < 600
I isPrime(s - 1) & s - 1 > :primes.last
:primes.append(s - 1)
I isPrime(s + 1) & s + 1 > :primes.last
:primes.append(s + 1)
s += 6
F nsmooth(n, size)
assert(n C 2..521)
assert(size >= 1)
V bn = n
V ok = 0B
L(prime) :primes
I bn == prime
ok = 1B
L.break
assert(ok, ‘must be a prime number’)
V ns = [BigInt(0)] * size
ns[0] = 1
[BigInt] next
L(prime) :primes
I prime > bn
L.break
next.append(prime)
V indicies = [0] * next.len
L(m) 1 .< size
ns[m] = min(next)
L(i) 0 .< indicies.len
I ns[m] == next[i]
indicies[i]++
next[i] = :primes[i] * ns[indicies[i]]
R ns
init()
L(p) primes
I p >= 30
L.break
print(‘The first ’p‘ -smooth numbers are:’)
print(nsmooth(p, 25))
print()
L(p) primes[1..]
I p >= 30
L.break
print(‘The 3000 to 3202 ’p‘ -smooth numbers are:’)
print(nsmooth(p, 3002)[2999..])
print()
L(p) [503, 509, 521]
print(‘The 30000 to 3019 ’p‘ -smooth numbers are:’)
print(nsmooth(p, 30019)[29999..])
print()</syntaxhighlight>
{{out}}
<pre>
The first 2 -smooth numbers are:
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216]
The first 3 -smooth numbers are:
[1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192]
The first 5 -smooth numbers are:
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54]
The first 7 -smooth numbers are:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36]
The first 11 -smooth numbers are:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32]
The first 13 -smooth numbers are:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28]
The first 17 -smooth numbers are:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27]
The first 19 -smooth numbers are:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26]
The first 23 -smooth numbers are:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
The first 29 -smooth numbers are:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
The 3000 to 3202 3 -smooth numbers are:
[91580367978306252441724649472, 92829823186414819915547541504, 94096325042746502515294076928]
The 3000 to 3202 5 -smooth numbers are:
[278942752080, 279936000000, 281250000000]
The 3000 to 3202 7 -smooth numbers are:
[50176000, 50331648, 50388480]
The 3000 to 3202 11 -smooth numbers are:
[2112880, 2116800, 2117016]
The 3000 to 3202 13 -smooth numbers are:
[390000, 390390, 390625]
The 3000 to 3202 17 -smooth numbers are:
[145800, 145860, 146016]
The 3000 to 3202 19 -smooth numbers are:
[74256, 74358, 74360]
The 3000 to 3202 23 -smooth numbers are:
[46552, 46575, 46585]
The 3000 to 3202 29 -smooth numbers are:
[33516, 33524, 33534]
The 30000 to 3019 503 -smooth numbers are:
[62913, 62914, 62916, 62918, 62920, 62923, 62926, 62928, 62930, 62933, 62935, 62937, 62944, 62946, 62951, 62952, 62953, 62957, 62959, 62964]
The 30000 to 3019 509 -smooth numbers are:
[62601, 62602, 62604, 62607, 62608, 62609, 62611, 62618, 62620, 62622, 62624, 62625, 62626, 62628, 62629, 62634, 62640, 62643, 62645, 62646]
The 30000 to 3019 521 -smooth numbers are:
[62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336]
</pre>
=={{header|C}}==
{{libheader|GMP}}
<
#include <stdint.h>
#include <stdio.h>
Line 180 ⟶ 331:
}
return 0;
}</
{{out}}
Line 216 ⟶ 367:
{{trans|D}}
The output for the 30,000 3-smooth numbers is not correct due to insuffiant bits to represent that actual value
<
#include <iostream>
#include <vector>
Line 348 ⟶ 499:
return 0;
}</
{{out}}
<pre>The first 2-smooth numbers are:
Line 409 ⟶ 560:
=={{header|C sharp|C#}}==
{{trans|D}}
<
using System.Collections.Generic;
using System.Linq;
Line 548 ⟶ 699:
}
}
}</
{{out}}
<pre>The first 2-smooth numbers are:
Line 618 ⟶ 769:
=={{header|Crystal}}==
{{trans|Ruby}}
<
def prime?(n)
return false unless (n | 1 == 3 if n < 5) || (n % 6)
pc = typeof(n).new(5)
return false if n % pc == 0 || n % (pc + 2) == 0
pc += 6
end
true
Line 673 ⟶ 824:
print nsmooth(prime, 30019)[29999..]
puts
end</
{{out}}
Line 718 ⟶ 869:
=={{header|D}}==
{{trans|Kotlin}}
<
import std.bigint;
import std.exception;
Line 836 ⟶ 987:
writeln;
}
}</
{{out}}
<pre>The first 2-smooth numbers are:
Line 909 ⟶ 1,060:
{{libheader| Velthuis.BigIntegers}}Thanks for Rudy Velthuis[https://github.com/rvelthuis/DelphiBigNumbers]
{{Trans|D}}
<syntaxhighlight lang="delphi">
program N_smooth_numbers;
Line 1,106 ⟶ 1,257:
Readln;
end.
</syntaxhighlight>
=={{header|Elm}}==
As mentioned on [[https://rosettacode.org/wiki/Hamming_numbers#Elm|the Hamming numbers task page]], currently Elm has many restrictions that make it difficult to implement finding a sequence of these numbers; as N-smooth numbers are just a more general case of Hamming numbers which include the latter, the code from that page is just re-factored to cover the more general case as follows:
<syntaxhighlight lang="elm">module Main exposing ( main )
import Bitwise exposing (..)
import BigInt exposing ( BigInt )
import Task exposing ( Task, succeed, perform, andThen )
import Html exposing ( div, text, br )
import Browser exposing ( element )
import Time exposing ( now, posixToMillis )
-- an infinite non-empty non-memoizing Co-Inductive Stream (CIS)...
type CIS a = CIS a (() -> CIS a)
takeCIS2String : Int -> (a -> String) -> CIS a -> String
takeCIS2String n cnvf (CIS ohd otlf) =
let loop i (CIS hd tl) str =
if i < 1 then str
else loop (i - 1) (tl()) (str ++ ", " ++ cnvf hd)
in loop (n - 1) (otlf()) (cnvf ohd)
dropCIS : Int -> CIS a -> CIS a
dropCIS n (CIS _ tl as cis) =
if n < 1 then cis else dropCIS (n - 1) (tl())
-- Priority Queue definition...
type PriorityQ comparable v =
Mt
| Br comparable v (PriorityQ comparable v)
(PriorityQ comparable v)
emptyPQ : PriorityQ comparable v
emptyPQ = Mt
peekMinPQ : PriorityQ comparable v -> Maybe (comparable, v)
peekMinPQ pq = case pq of
(Br k v _ _) -> Just (k, v)
Mt -> Nothing
pushPQ : comparable -> v -> PriorityQ comparable v
-> PriorityQ comparable v
pushPQ wk wv pq =
case pq of
Mt -> Br wk wv Mt Mt
(Br vk vv pl pr) ->
if wk <= vk then Br wk wv (pushPQ vk vv pr) pl
else Br vk vv (pushPQ wk wv pr) pl
siftdown : comparable -> v -> PriorityQ comparable v
-> PriorityQ comparable v -> PriorityQ comparable v
siftdown wk wv pql pqr =
case pql of
Mt -> Br wk wv Mt Mt
(Br vkl vvl pll prl) ->
case pqr of
Mt -> if wk <= vkl then Br wk wv pql Mt
else Br vkl vvl (Br wk wv Mt Mt) Mt
(Br vkr vvr plr prr) ->
if wk <= vkl && wk <= vkr then Br wk wv pql pqr
else if vkl <= vkr then Br vkl vvl (siftdown wk wv pll prl) pqr
else Br vkr vvr pql (siftdown wk wv plr prr)
replaceMinPQ : comparable -> v -> PriorityQ comparable v
-> PriorityQ comparable v
replaceMinPQ wk wv pq = case pq of
Mt -> Mt
(Br _ _ pl pr) -> siftdown wk wv pl pr
primesTo : Int -> List Int
primesTo n =
if n < 3 then if n < 2 then [] else [2] else
let oddPrimesTo on =
let sqrtlmt = toFloat on |> sqrt |> truncate
obps = if sqrtlmt < 3 then [] else oddPrimesTo sqrtlmt
ns = List.range 0 ((on - 3) // 2) -- [ 3 .. 2 .. on ]
|> List.map ((+) 3 << (*) 2)
filtfnc fn = List.all (\ bp -> bp * bp > fn ||
modBy bp fn /= 0) obps
in List.filter filtfnc ns
in 2 :: oddPrimesTo n
smooths : Int -> CIS BigInt
smooths n =
let infcis v = CIS v <| \ _ -> infcis (BigInt.add v (BigInt.fromInt 1))
dflt = (0.0, BigInt.fromInt 1) in
if n < 2 then infcis (BigInt.fromInt 1) else
let prms = primesTo n |> List.reverse
|> List.map (\ p -> (logBase 2 (toFloat p), BigInt.fromInt p))
((lgfrstp, frstp) as frstpr) = List.head prms |> Maybe.withDefault dflt
rstps = List.tail prms |> Maybe.withDefault []
frstcis =
let nxt ((lg, v) as vpr) =
CIS vpr <| \ _ -> nxt (lg + lgfrstp, BigInt.mul v frstp)
in nxt frstpr
mkcis ((lg, p) as pr) cis =
let nxt pq (CIS ((lghd, hd) as hdpr) tlf as cs) =
let ((lgv, v) as vpr) = peekMinPQ pq |> Maybe.withDefault dflt in
if BigInt.lt v hd then CIS vpr <| \ _ ->
nxt (replaceMinPQ (lgv + lg) (BigInt.mul v p) pq) cs
else CIS hdpr <| \ _ ->
nxt (pushPQ (lghd + lg) (BigInt.mul hd p) pq) (tlf())
in CIS pr <| \ _ -> nxt (pushPQ (lg + lg) (BigInt.mul p p) emptyPQ) cis
rest() = List.foldl mkcis frstcis rstps
unpr (CIS (_, hd) tlf) = CIS hd <| \ _ -> unpr (tlf())
in CIS (BigInt.fromInt 1) <| \ _ -> unpr (rest())
timemillis : () -> Task Never Int -- a side effect function
timemillis() = now |> andThen (\ t -> succeed (posixToMillis t))
test : () -> Cmd Msg -- side effect function chain (includes "perform")...
test() =
timemillis()
|> andThen (\ strt ->
let test1 = primesTo 29 |> List.map ( \ p ->
[ "The first 25 " ++ String.fromInt p ++ "-smooths:"
, smooths p |> takeCIS2String 25 BigInt.toString
, "" ])
test2 = primesTo 29 |> List.drop 1 |> List.map ( \ p ->
[ "The first three from the 3,000th "
++ String.fromInt p ++ "-smooth numbers are:"
, smooths p |> dropCIS 2999
|> takeCIS2String 3 BigInt.toString
, "" ])
test3 = primesTo 521 |> List.filter ((<=) 503) |> List.map ( \ p ->
[ "The first 20 30,000th up "
++ String.fromInt p ++ "-smooth numbers are:"
, smooths p |> dropCIS 29999
|> takeCIS2String 20 BigInt.toString
, "" ])
in timemillis()
|> andThen (\ stop ->
succeed ([test1, test2, test3, [[ "This took "
++ String.fromInt (stop - strt)
++ " milliseconds."]]]
|> List.concat |> List.concat)))
|> perform Done
-- following code has to do with outputting to a web page using MUV/TEA...
type alias Model = List String
type Msg = Done Model
main : Program () Model Msg
main = -- starts with empty list of strings; views model of filled list...
element { init = \ _ -> ( [], test() )
, update = \ (Done mdl) _ -> ( mdl , Cmd.none )
, subscriptions = \ _ -> Sub.none
, view = \ mdl ->
div [] <| List.map (\ s ->
if s == "" then br [] []
else div [] <| List.singleton <| text s) mdl
}</syntaxhighlight>
{{out}}
<pre>The first 25 13-smooths:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28
The first 25 17-smooths:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27
The first 25 19-smooths:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26
The first 25 23-smooths:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25
The first 25 29-smooths:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25
The first three from the 3,000th 3-smooth numbers are:
91580367978306252441724649472, 92829823186414819915547541504, 94096325042746502515294076928
The first three from the 3,000th 5-smooth numbers are:
278942752080, 279936000000, 281250000000
The first three from the 3,000th 7-smooth numbers are:
50176000, 50331648, 50388480
The first three from the 3,000th 11-smooth numbers are:
2112880, 2116800, 2117016
The first three from the 3,000th 13-smooth numbers are:
390000, 390390, 390625
The first three from the 3,000th 17-smooth numbers are:
145800, 145860, 146016
The first three from the 3,000th 19-smooth numbers are:
74256, 74358, 74360
The first three from the 3,000th 23-smooth numbers are:
46552, 46575, 46585
The first three from the 3,000th 29-smooth numbers are:
33516, 33524, 33534
The first 20 30,000th up 503-smooth numbers are:
62913, 62914, 62916, 62918, 62920, 62923, 62926, 62928, 62930, 62933, 62935, 62937, 62944, 62946, 62951, 62952, 62953, 62957, 62959, 62964
The first 20 30,000th up 509-smooth numbers are:
62601, 62602, 62604, 62607, 62608, 62609, 62611, 62618, 62620, 62622, 62624, 62625, 62626, 62628, 62629, 62634, 62640, 62643, 62645, 62646
The first 20 30,000th up 521-smooth numbers are:
62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336
This took 506 milliseconds.</pre>
=={{header|F_Sharp|F#}}==
The easy way to solve this is just to translate the Haskell contribution as from "Hamming Numbers without duplicates", along with a version of a trial division small primes determination since the required primes have such a small range, as follows:
<syntaxhighlight lang="fsharp">let primesTo n =
if n < 3 then (if n < 2 then Seq.empty else Seq.singleton 2) else
let rec oddPrimesTo on =
let sqrtlmt = double on |> sqrt |> truncate |> int
let obps = if sqrtlmt < 3 then Seq.empty else oddPrimesTo sqrtlmt
let ns = [ 3 .. 2 .. on ]
let filtfnc fn = Seq.forall (fun bp -> bp * bp > fn ||
fn % bp <> 0) obps
Seq.filter filtfnc ns
Seq.append (Seq.singleton 2) (oddPrimesTo n)
type LazyList<'a> = Cons of 'a * Lazy<LazyList<'a>>
// Doesn't need to be that efficient for the task...
#nowarn "40" // don't need to warn for recursive values
let smooths p =
if p < 2 then Seq.singleton (bigint 1) else
let smthprms = primesTo p |> Seq.rev |> Seq.map bigint
let frstp = Seq.head smthprms
let rstps = Seq.tail smthprms
let frstll =
let rec nxt n =
Cons(n, lazy nxt (n * frstp))
nxt frstp
let smult m lzylst =
let rec smlt (Cons(x, rxs)) =
Cons(m * x, lazy(smlt (rxs.Force())))
smlt lzylst
let rec merge (Cons(x, f) as xs) (Cons(y, g) as ys) =
if x < y then Cons(x, lazy(merge (f.Force()) ys))
else Cons(y, lazy(merge xs (g.Force())))
let u s n =
let rec r = merge s (smult n (Cons(1I, lazy r))) in r
Seq.unfold (fun (Cons(hd, rst)) -> Some (hd, rst.Value))
(Cons(1I, lazy(Seq.fold u frstll rstps)))
let strt = System.DateTime.Now.Ticks
primesTo 29 |> Seq.iter (fun p ->
printfn "First 25 %d-smooth:" p
smooths p |> Seq.take 25 |> Seq.toList |> printfn "%A\r\n")
primesTo 29 |> Seq.skip 1 |> Seq.iter (fun p ->
printfn "The first three from the 3,000th %d-smooth numbers are:" p
smooths p |> Seq.skip 2999 |> Seq.take 3 |> Seq.toList |> printfn "%A\r\n")
primesTo 521 |> Seq.skipWhile ((>) 503) |> Seq.iter (fun p ->
printfn "The first 20 30,000th up %d-smooth numbers are:" p
smooths p |> Seq.skip 29999 |> Seq.take 20 |> Seq.toList |> printfn "%A\r\n")
let stop = System.DateTime.Now.Ticks
printfn "This took %d milliseconds." ((stop - strt) / 10000L)</syntaxhighlight>
{{out}}
<pre>First 25 2-smooth:
[1; 2; 4; 8; 16; 32; 64; 128; 256; 512; 1024; 2048; 4096; 8192; 16384; 32768;
65536; 131072; 262144; 524288; 1048576; 2097152; 4194304; 8388608; 16777216]
First 25 3-smooth:
[1; 2; 3; 4; 6; 8; 9; 12; 16; 18; 24; 27; 32; 36; 48; 54; 64; 72; 81; 96; 108;
128; 144; 162; 192]
First 25 5-smooth:
[1; 2; 3; 4; 5; 6; 8; 9; 10; 12; 15; 16; 18; 20; 24; 25; 27; 30; 32; 36; 40; 45;
48; 50; 54]
First 25 7-smooth:
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 12; 14; 15; 16; 18; 20; 21; 24; 25; 27; 28; 30;
32; 35; 36]
First 25 11-smooth:
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 14; 15; 16; 18; 20; 21; 22; 24; 25; 27;
28; 30; 32]
First 25 13-smooth:
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 18; 20; 21; 22; 24; 25;
26; 27; 28]
First 25 17-smooth:
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 20; 21; 22; 24;
25; 26; 27]
First 25 19-smooth:
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22;
24; 25; 26]
First 25 23-smooth:
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22;
23; 24; 25]
First 25 29-smooth:
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22;
23; 24; 25]
The first three from the 3,000th 3-smooth numbers are:
[91580367978306252441724649472; 92829823186414819915547541504;
94096325042746502515294076928]
The first three from the 3,000th 5-smooth numbers are:
[278942752080; 279936000000; 281250000000]
The first three from the 3,000th 7-smooth numbers are:
[50176000; 50331648; 50388480]
The first three from the 3,000th 11-smooth numbers are:
[2112880; 2116800; 2117016]
The first three from the 3,000th 13-smooth numbers are:
[390000; 390390; 390625]
The first three from the 3,000th 17-smooth numbers are:
[145800; 145860; 146016]
The first three from the 3,000th 19-smooth numbers are:
[74256; 74358; 74360]
The first three from the 3,000th 23-smooth numbers are:
[46552; 46575; 46585]
The first three from the 3,000th 29-smooth numbers are:
[33516; 33524; 33534]
The first 20 30,000th up 503-smooth numbers are:
[62913; 62914; 62916; 62918; 62920; 62923; 62926; 62928; 62930; 62933; 62935;
62937; 62944; 62946; 62951; 62952; 62953; 62957; 62959; 62964]
The first 20 30,000th up 509-smooth numbers are:
[62601; 62602; 62604; 62607; 62608; 62609; 62611; 62618; 62620; 62622; 62624;
62625; 62626; 62628; 62629; 62634; 62640; 62643; 62645; 62646]
The first 20 30,000th up 521-smooth numbers are:
[62287; 62288; 62291; 62292; 62300; 62304; 62307; 62308; 62310; 62315; 62320;
62321; 62322; 62325; 62328; 62329; 62330; 62331; 62335; 62336]
This took 544 milliseconds.</pre>
As run on an Intel i5-6500 (3.6 GHz boosted when single-threaded), this isn't particularly fast, slowed by DotNet's poor allocation/deallocation of small memory area performance as required here for the "LazyList" implementation (a new allocation for each element) as well as the time to process the deferred execution "thunks" required for memoization, and also because the "BigInt" implementation isn't likely as fast as the "native" implementation used by some languages such as Haskell (by default).
'''Faster Non-recursive Version'''
The following code is over twice as fast because it no longer requires a memoized "LazyList" but just the deferred-execution tails of a Co-Inductive Stream (CIS), although to be general it still uses these streams for each merged CIS of the accumulated intermediate result streams, meaning that it still uses many allocations/deallocations for each CIS element; as well, it avoids some of the slow F# "Seq" operations by directly manipulating the "CIS" streams:
<syntaxhighlight lang="fsharp">let primesTo n =
if n < 3 then (if n < 2 then Seq.empty else Seq.singleton 2) else
let rec oddPrimesTo on =
let sqrtlmt = double on |> sqrt |> truncate |> int
let obps = if sqrtlmt < 3 then Seq.empty else oddPrimesTo sqrtlmt
let ns = [ 3 .. 2 .. on ]
let filtfnc fn = Seq.forall (fun bp -> bp * bp > fn ||
fn % bp <> 0) obps
Seq.filter filtfnc ns
Seq.append (Seq.singleton 2) (oddPrimesTo n)
type CIS<'a> = CIS of 'a * (Unit -> CIS<'a>)
let rec skipCIS n (CIS(_, tlf) as cis) =
if n <= 0 then cis else skipCIS (n - 1) (tlf())
let stringCIS n (CIS(fhd, ftlf)) =
let rec addstr i (CIS(hd, tlf)) str =
if i <= 0 then str + " )"
else addstr (i - 1) (tlf()) (str + ", " + string hd)
addstr (n - 1) (ftlf()) ("( " + string fhd)
type Deque<'a> = Deque of int * int * int * 'a array
let makeDQ v =
let arr = Array.zeroCreate 1024 in arr.[0] <- v
Deque(1023, 0, 1, arr)
let growDQ (Deque(msk, hdi, tli, arr)) =
let sz = arr.Length
let nsz = if sz = 0 then 1024 else sz + sz
let narr = Array.zeroCreate nsz
let nhdi, ntli =
if hdi = 0 then Array.blit arr 0 narr 0 sz
hdi, sz
else let mv = hdi + sz // move top queue up...
Array.blit arr 0 narr 0 tli
Array.blit arr hdi narr mv (sz - hdi)
mv, tli
Deque(nsz - 1, nhdi, ntli, narr)
let pushDQ v (Deque(_, hdi, tli, _) as dq) =
let (Deque(nmsk, nhdi, ntli, narr)) = if tli <> hdi then dq
else growDQ dq
narr.[ntli] <- v
Deque(nmsk, nhdi, (ntli + 1) &&& nmsk, narr)
// Deque is never empty after the first push and always push before pull!
let inline peekDQ (Deque(_, hdi, _, arr)) = arr.[hdi]
let pullDQ (Deque(msk, hdi, tli, arr)) =
Deque(msk, (hdi + 1) &&& msk, tli, arr)
let smoothsNR p =
// if p < 2 then Seq.singleton (bigint 1) else
let smthprms = primesTo p |> Seq.rev |> Seq.map bigint
let frstp = Seq.head smthprms
let rstps = Seq.tail smthprms
let frstcis =
let rec nxt n =
CIS(n, fun () -> nxt (n * frstp)) in nxt frstp
let nxt dq =
Seq.initInfinite ((+) 1I << bigint)
let newcis cis p =
let rec nxt (CIS(hd, tlf) as cs) dq =
let nxtq = peekDQ dq
if hd < nxtq then CIS(hd, fun () -> nxt (tlf()) (pushDQ (hd * p) dq))
else CIS(nxtq, fun () -> nxt cs (pushDQ (nxtq * p) dq |> pullDQ))
CIS(p, fun () -> nxt cis (makeDQ (p * p)))
CIS(1I, fun () -> Seq.fold newcis frstcis rstps)
let strt = System.DateTime.Now.Ticks
primesTo 29 |> Seq.iter (fun p ->
printfn "First 25 %d-smooth:" p
smoothsNR p |> stringCIS 25 |> printfn "%s\r\n")
primesTo 29 |> Seq.skip 1 |> Seq.iter (fun p ->
printfn "The first three from the 3,000th %d-smooth numbers are:" p
smoothsNR p |> skipCIS 2999 |> stringCIS 3 |> printfn "%s\r\n")
primesTo 521 |> Seq.skipWhile ((>) 503) |> Seq.iter (fun p ->
printfn "The first 20 from the 30,000th up %d-smooth numbers are:" p
smoothsNR p |> skipCIS 29999 |> stringCIS 20 |> printfn "%s\r\n")
let stop = System.DateTime.Now.Ticks
printfn "This took %d milliseconds." ((stop - strt) / 10000L)</syntaxhighlight>
=={{header|Factor}}==
<
math.order math.primes math.text.english namespaces prettyprint
sequences tools.memory.private ;
Line 1,147 ⟶ 1,735:
503 521 30,000 30,019 show-smooth ;
MAIN: smooth-numbers-demo</
{{out}}
<pre>
Line 1,177 ⟶ 1,765:
=={{header|Go}}==
<
import (
Line 1,275 ⟶ 1,863:
fmt.Println(nSmooth(i, 30019)[29999:], "\n")
}
}</
{{out}}
Line 1,348 ⟶ 1,936:
The solution is based on the hamming numbers solution [[Hamming_numbers#Avoiding_generation_of_duplicates]].<br>
Uses Library Data.Number.Primes: http://hackage.haskell.org/package/primes-0.2.1.0/docs/Data-Numbers-Primes.html
<
import Text.Printf (printf)
Line 1,377 ⟶ 1,965:
showTwentyFive = show . take 25 . nSmooth
showRange1 = show . ((<$> [2999 .. 3001]) . (!!) . nSmooth)
showRange2 = show . ((<$> [29999 .. 30018]) . (!!) . nSmooth)</
{{out}}
<pre>
Line 1,454 ⟶ 2,042:
=={{header|J}}==
This solution involves sorting, duplicate removal, and limits on the number of preserved terms.
<syntaxhighlight lang="j">
nsmooth=: dyad define NB. TALLY nsmooth N
factors=. x: i.@:>:&.:(p:inv) y
Line 1,465 ⟶ 2,053:
end.
)
</syntaxhighlight>
<pre style="white-space: pre; overflow-x: overflow">
25 (] ; nsmooth)&> p: i. 10
┌──┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
Line 1,515 ⟶ 2,103:
=={{header|Java}}==
<
import java.math.BigInteger;
import java.util.ArrayList;
Line 1,620 ⟶ 2,208:
}
</syntaxhighlight>
{{out}}
Line 1,692 ⟶ 2,280:
The 30000 through 30019 521-smooth numbers:
62287 62288 62291 62292 62300 62304 62307 62308 62310 62315 62320 62321 62322 62325 62328 62329 62330 62331 62335 62336
</pre>
=={{header|JavaScript}}==
<syntaxhighlight lang="javascript">
function isPrime(n){
var x = Math.floor(Math.sqrt(n)), i = 2
while ((i <= x) && (n % i != 0)) i++
return (x < i)
}
function smooth(n, s, k){
var p = []
for (let i = 2; i <= n; i++){
if (isPrime(i)){
p.push([BigInt(i), [1n], 0])
}
}
var res = []
for (let i = 0; i < s + k; i++){
var m = p[0][1][p[0][2]]
for (let j = 1; j < p.length; j++){
if (p[j][1][p[j][2]] < m) m = p[j][1][p[j][2]]
}
for (let j = 0; j < p.length; j++){
p[j][1].push(p[j][0]*m)
if (p[j][1][p[j][2]] == m) p[j][2]++
}
res.push(m)
}
return res.slice(s-1, s-1+k);
}
// main
var sOut = ""
for (let x of [[2, 29, 1, 25], [3, 29, 3000, 3], [503, 521, 30000, 20]]){
for (let n = x[0]; n <= x[1]; n++){
if (isPrime(n)){
sOut += x[2] + " to " + (x[2] - 1 + x[3]) + " " + n + "-smooth numbers: " + smooth(n, x[2], x[3]) + "\n"
}
}
}
console.log(sOut)
</syntaxhighlight>
{{out}}
<pre>
1 to 25 2-smooth numbers: 1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216
1 to 25 3-smooth numbers: 1,2,3,4,6,8,9,12,16,18,24,27,32,36,48,54,64,72,81,96,108,128,144,162,192
1 to 25 5-smooth numbers: 1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54
1 to 25 7-smooth numbers: 1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,28,30,32,35,36
1 to 25 11-smooth numbers: 1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,18,20,21,22,24,25,27,28,30,32
1 to 25 13-smooth numbers: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,20,21,22,24,25,26,27,28
1 to 25 17-smooth numbers: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,20,21,22,24,25,26,27
1 to 25 19-smooth numbers: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26
1 to 25 23-smooth numbers: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25
1 to 25 29-smooth numbers: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25
3000 to 3002 3-smooth numbers: 91580367978306252441724649472,92829823186414819915547541504,94096325042746502515294076928
3000 to 3002 5-smooth numbers: 278942752080,279936000000,281250000000
3000 to 3002 7-smooth numbers: 50176000,50331648,50388480
3000 to 3002 11-smooth numbers: 2112880,2116800,2117016
3000 to 3002 13-smooth numbers: 390000,390390,390625
3000 to 3002 17-smooth numbers: 145800,145860,146016
3000 to 3002 19-smooth numbers: 74256,74358,74360
3000 to 3002 23-smooth numbers: 46552,46575,46585
3000 to 3002 29-smooth numbers: 33516,33524,33534
30000 to 30019 503-smooth numbers: 62913,62914,62916,62918,62920,62923,62926,62928,62930,62933,62935,62937,62944,62946,62951,62952,62953,62957,62959,62964
30000 to 30019 509-smooth numbers: 62601,62602,62604,62607,62608,62609,62611,62618,62620,62622,62624,62625,62626,62628,62629,62634,62640,62643,62645,62646
30000 to 30019 521-smooth numbers: 62287,62288,62291,62292,62300,62304,62307,62308,62310,62315,62320,62321,62322,62325,62328,62329,62330,62331,62335,62336
</pre>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
'''Works with gojq, the Go implementation of jq'''
The output shown below is from a run of gojq, which has unbounded-precision arithmetic.
The C implementation of jq produces the same results for the first task (namely showing the first 125 n-smooth numbers for n <= 29), but not for the subsequent task.
<syntaxhighlight lang=jq>
def select_while(s; cond):
label $out | s | if cond then . else break $out end;
### Some primes
# 168 small primes
def small_primes: [
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
];
### n-smooth numbers
def nSmooth($n; $size):
small_primes[-1] as $maxn
| if $n < 2 or $n > $maxn then "nSmooth: n must be in 2 .. \($maxn) inclusive" | error
elif ($size < 1) then "nSmooth: size must be at least 1" | error
elif any(small_primes[]; $n == .) | not then "nSmooth: n must be a prime number" | error
else (small_primes|length) as $length
| {ns: [1, (range(1; $size)|null)],
i: 0,
next: [] }
| until(.done or .i == $length;
if (small_primes[.i] > $n) then .done = true
else .next += [small_primes[.i]]
| .i += 1
end )
| .indices = [range(0; .next|length) | 0]
| reduce range(1; $size) as $m (.;
.ns[$m] = (.next | min)
| reduce range(0; .indices|length) as $i (.;
if (.ns[$m] == .next[$i])
then .indices[$i] += 1
| .next[$i] = small_primes[$i] * .ns[.indices[$i]]
else .
end ))
| .ns
end;
def task:
[select_while(small_primes[]; . <= 29)] as $smallPrimes
| ($smallPrimes[]
| "\nThe first 25 \(.)-smooth numbers are:",
nSmooth(.; 25)),
"",
($smallPrimes[1:][]
| "\nThe 3,000th to 3,202nd \(.)-smooth numbers are:",
nSmooth(.; 3002)[2999:] ),
"",
( (503, 509, 521)
|"\nThe 30,000th to 30,019th \(.)-smooth numbers are:",
nSmooth(.; 30019)[29999:] ) ;
task
</syntaxhighlight>
{{output}}
Invocation: gojq -nrcf n-smooth-numbers.jq
<pre style="height:20lh;overflow:auto>
The first 25 2-smooth numbers are:
[1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216]
The first 25 3-smooth numbers are:
[1,2,3,4,6,8,9,12,16,18,24,27,32,36,48,54,64,72,81,96,108,128,144,162,192]
The first 25 5-smooth numbers are:
[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54]
The first 25 7-smooth numbers are:
[1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,28,30,32,35,36]
The first 25 11-smooth numbers are:
[1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,18,20,21,22,24,25,27,28,30,32]
The first 25 13-smooth numbers are:
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,20,21,22,24,25,26,27,28]
The first 25 17-smooth numbers are:
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,20,21,22,24,25,26,27]
The first 25 19-smooth numbers are:
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26]
The first 25 23-smooth numbers are:
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25]
The first 25 29-smooth numbers are:
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25]
The 3,000th to 3,202nd 3-smooth numbers are:
[91580367978306252441724649472,92829823186414819915547541504,94096325042746502515294076928]
The 3,000th to 3,202nd 5-smooth numbers are:
[278942752080,279936000000,281250000000]
The 3,000th to 3,202nd 7-smooth numbers are:
[50176000,50331648,50388480]
The 3,000th to 3,202nd 11-smooth numbers are:
[2112880,2116800,2117016]
The 3,000th to 3,202nd 13-smooth numbers are:
[390000,390390,390625]
The 3,000th to 3,202nd 17-smooth numbers are:
[145800,145860,146016]
The 3,000th to 3,202nd 19-smooth numbers are:
[74256,74358,74360]
The 3,000th to 3,202nd 23-smooth numbers are:
[46552,46575,46585]
The 3,000th to 3,202nd 29-smooth numbers are:
[33516,33524,33534]
The 30,000th to 30,019th 503-smooth numbers are:
[62913,62914,62916,62918,62920,62923,62926,62928,62930,62933,62935,62937,62944,62946,62951,62952,62953,62957,62959,62964]
The 30,000th to 30,019th 509-smooth numbers are:
[62601,62602,62604,62607,62608,62609,62611,62618,62620,62622,62624,62625,62626,62628,62629,62634,62640,62643,62645,62646]
The 30,000th to 30,019th 521-smooth numbers are:
[62287,62288,62291,62292,62300,62304,62307,62308,62310,62315,62320,62321,62322,62325,62328,62329,62330,62331,62335,62336]
</pre>
=={{header|Julia}}==
<
function nsmooth(N, needed)
Line 1,725 ⟶ 2,533:
testnsmoothfilters()
</
<pre>
The first 25 n-smooth numbers for n = 2 are: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216]
Line 1,753 ⟶ 2,561:
=={{header|Kotlin}}==
{{trans|Go}}
<
var primes = mutableListOf<BigInteger>()
Line 1,845 ⟶ 2,653:
println()
}
}</
{{out}}
<pre>The first 25 2-smooth numbers are:
Line 1,912 ⟶ 2,720:
The 30,000th to 30,019 521-smooth numbers are:
[62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336]</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[GenerateSmoothNumbers]
GenerateSmoothNumbers[max_?Positive] := GenerateSmoothNumbers[max, 7]
GenerateSmoothNumbers[max_?Positive, maxprime_?Positive] :=
Module[{primes, len, vars, body, endspecs, its, data},
primes = Prime[Range[PrimePi[maxprime]]];
len = Length[primes];
If[max < Min[primes],
{}
,
vars = Table[Unique[], len];
body = Times @@ (primes^vars);
endspecs = Prepend[Most[primes^vars], 1];
endspecs = FoldList[Times, endspecs];
its = Transpose[{vars, ConstantArray[0, len], MapThread[N@Log[#1, max/#2] &, {primes, endspecs}]}];
With[{b = body, is = its},
data = Table[b, Evaluate[Sequence @@ is]];
];
data = Sort[Flatten[data]];
data
]
]
Take[GenerateSmoothNumbers[10^8, 2], 25]
Take[GenerateSmoothNumbers[200, 3], 25]
Take[GenerateSmoothNumbers[200, 5], 25]
Take[GenerateSmoothNumbers[200, 7], 25]
Take[GenerateSmoothNumbers[200, 11], 25]
Take[GenerateSmoothNumbers[200, 13], 25]
Take[GenerateSmoothNumbers[200, 17], 25]
Take[GenerateSmoothNumbers[200, 19], 25]
Take[GenerateSmoothNumbers[200, 23], 25]
Take[GenerateSmoothNumbers[200, 29], 25]
Take[GenerateSmoothNumbers[10^40, 3], {3000, 3002}]
Take[GenerateSmoothNumbers[10^15, 5], {3000, 3002}]
Take[GenerateSmoothNumbers[10^10, 7], {3000, 3002}]
Take[GenerateSmoothNumbers[10^7, 11], {3000, 3002}]
Take[GenerateSmoothNumbers[10^7, 13], {3000, 3002}]
Take[GenerateSmoothNumbers[10^6, 17], {3000, 3002}]
Take[GenerateSmoothNumbers[10^5, 19], {3000, 3002}]
Take[GenerateSmoothNumbers[10^5, 23], {3000, 3002}]
Take[GenerateSmoothNumbers[10^5, 29], {3000, 3002}]
s = Select[Range[10^5], FactorInteger /* Last /* First /* LessEqualThan[503]];
s[[30000 ;; 30019]]
s = Select[Range[10^5], FactorInteger /* Last /* First /* LessEqualThan[509]];
s[[30000 ;; 30019]]
s = Select[Range[10^5], FactorInteger /* Last /* First /* LessEqualThan[521]];
s[[30000 ;; 30019]]</syntaxhighlight>
{{out}}
<pre>{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216}
{1,2,3,4,6,8,9,12,16,18,24,27,32,36,48,54,64,72,81,96,108,128,144,162,192}
{1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54}
{1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,28,30,32,35,36}
{1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,18,20,21,22,24,25,27,28,30,32}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,20,21,22,24,25,26,27,28}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,20,21,22,24,25,26,27}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25}
{91580367978306252441724649472,92829823186414819915547541504,94096325042746502515294076928}
{278942752080,279936000000,281250000000}
{50176000,50331648,50388480}
{2112880,2116800,2117016}
{390000,390390,390625}
{145800,145860,146016}
{74256,74358,74360}
{46552,46575,46585}
{33516,33524,33534}
{62913,62914,62916,62918,62920,62923,62926,62928,62930,62933,62935,62937,62944,62946,62951,62952,62953,62957,62959,62964}
{62601,62602,62604,62607,62608,62609,62611,62618,62620,62622,62624,62625,62626,62628,62629,62634,62640,62643,62645,62646}
{62287,62288,62291,62292,62300,62304,62307,62308,62310,62315,62320,62321,62322,62325,62328,62329,62330,62331,62335,62336}</pre>
=={{header|Nim}}==
{{trans|Kotlin}}
{{libheader|bignum}}
Translation of Kotlin except for the search of primes where we have chosen to use a sieve of Eratosthenes.
<syntaxhighlight lang="nim">import sequtils, strutils
import bignum
const N = 521
func initPrimes(): tuple[primes: seq[Int]; smallPrimes: seq[int]] =
var sieve: array[2..N, bool]
for n in 2..N:
if not sieve[n]:
for k in countup(n * n, N, n): sieve[k] = true
for n, isComposite in sieve:
if not isComposite:
result.primes.add newInt(n)
if n <= 29: result.smallPrimes.add n
# Cache all primes up to N.
let (Primes, SmallPrimes) = initPrimes()
proc nSmooth(n, size: Positive): seq[Int] =
assert n in 2..N, "'n' must be between 2 and " & $N
let bn = newInt(n)
assert bn in Primes, "'n' must be a prime number"
result.setLen(size)
result[0] = newInt(1)
var next: seq[Int]
for prime in Primes:
if prime > bn: break
next.add prime
var indices = newSeq[int](next.len)
for m in 1..<size:
result[m] = next[next.minIndex()]
for i in 0..indices.high:
if result[m] == next[i]:
inc indices[i]
next[i] = Primes[i] * result[indices[i]]
when isMainModule:
for n in SmallPrimes:
echo "The first ", n, "-smooth numbers are:"
echo nSmooth(n, 25).join(" ")
echo ""
for n in SmallPrimes[1..^1]:
echo "The 3000th to 3202th ", n, "-smooth numbers are:"
echo nSmooth(n, 3002)[2999..^1].join(" ")
echo ""
for n in [503, 509, 521]:
echo "The 30000th to 30019th ", n, "-smooth numbers are:"
echo nSmooth(n, 30_019)[29_999..^1].join(" ")
echo ""</syntaxhighlight>
{{out}}
<pre>The first 2-smooth numbers are:
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216
The first 3-smooth numbers are:
1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96 108 128 144 162 192
The first 5-smooth numbers are:
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54
The first 7-smooth numbers are:
1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36
The first 11-smooth numbers are:
1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32
The first 13-smooth numbers are:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20 21 22 24 25 26 27 28
The first 17-smooth numbers are:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 25 26 27
The first 19-smooth numbers are:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26
The first 23-smooth numbers are:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
The first 29-smooth numbers are:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
The 3000th to 3202th 3-smooth numbers are:
91580367978306252441724649472 92829823186414819915547541504 94096325042746502515294076928
The 3000th to 3202th 5-smooth numbers are:
278942752080 279936000000 281250000000
The 3000th to 3202th 7-smooth numbers are:
50176000 50331648 50388480
The 3000th to 3202th 11-smooth numbers are:
2112880 2116800 2117016
The 3000th to 3202th 13-smooth numbers are:
390000 390390 390625
The 3000th to 3202th 17-smooth numbers are:
145800 145860 146016
The 3000th to 3202th 19-smooth numbers are:
74256 74358 74360
The 3000th to 3202th 23-smooth numbers are:
46552 46575 46585
The 3000th to 3202th 29-smooth numbers are:
33516 33524 33534
The 30000th to 30019th 503-smooth numbers are:
62913 62914 62916 62918 62920 62923 62926 62928 62930 62933 62935 62937 62944 62946 62951 62952 62953 62957 62959 62964
The 30000th to 30019th 509-smooth numbers are:
62601 62602 62604 62607 62608 62609 62611 62618 62620 62622 62624 62625 62626 62628 62629 62634 62640 62643 62645 62646
The 30000th to 30019th 521-smooth numbers are:
62287 62288 62291 62292 62300 62304 62307 62308 62310 62315 62320 62321 62322 62325 62328 62329 62330 62331 62335 62336
</pre>
=={{header|PARI/GP}}==
<syntaxhighlight lang="pari">
Vi__smooth(V0, C)= {
my( W= #V0, V_r= Vec([1],C), v= V0, ix= vector(W,i,1), t);
for( c= 2, C
, V_r[c]= t= vecmin(v);
for( w= 1, W
, if( v[w] == t, v[w]= V0[w] * V_r[ ix[w]++ ]);
);
);
V_r;
}
N_smooth(N, C=20, S=1)= Vi__smooth(primes([0,N]),S+C-1)[S..S+C-1];
[print(v) |v<-[N_smooth(N, 25) |N<-primes([ 2, 29])]];
[print(v) |v<-[N_smooth(N, 3, 3000) |N<-primes([ 3, 29])]];
[print(v) |v<-[N_smooth(N, 20, 30000) |N<-primes([503,521])]];
</syntaxhighlight>
{{out}}
<pre>
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216]
[1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192]
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
[91580367978306252441724649472, 92829823186414819915547541504, 94096325042746502515294076928]
[278942752080, 279936000000, 281250000000]
[50176000, 50331648, 50388480]
[2112880, 2116800, 2117016]
[390000, 390390, 390625]
[145800, 145860, 146016]
[74256, 74358, 74360]
[46552, 46575, 46585]
[33516, 33524, 33534]
[62913, 62914, 62916, 62918, 62920, 62923, 62926, 62928, 62930, 62933, 62935, 62937, 62944, 62946, 62951, 62952, 62953, 62957, 62959, 62964]
[62601, 62602, 62604, 62607, 62608, 62609, 62611, 62618, 62620, 62622, 62624, 62625, 62626, 62628, 62629, 62634, 62640, 62643, 62645, 62646]
[62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336]
</pre>
=={{header|Pascal}}==
==={{header|Extended Pascal}}===
<syntaxhighlight lang="pascal">program nSmoothNumbers(output);
const
primeCount = 538;
{$ifDef __GPC__} {$setLimit=3889} {$endIf}
cardinalMax = 3888;
type
cardinal = 0..cardinalMax;
cardinals = set of cardinal;
cardinalPositive = 1..cardinalMax;
natural = 1..maxInt;
primeIndex = 1..primeCount;
list = array[primeIndex] of cardinal;
var
prime: list;
{
\brief performs prime factorization
\param n the number to factorize
\return list of exponents for a unique integer factorization using primes
This function requires the global `prime` variable to be initialized.
}
function primeFactorization(n: natural): list;
var
i: primeIndex;
{
Instead of writing `[1: 0; 2: 0; 3: 0; …]`, Extended Pascal permits us
to use an “array completer” for all unspecified values.
}
result: list value [otherwise 0];
begin
for i := 1 to primeCount do
begin
while n mod prime[i] = 0 do
begin
n := n div prime[i];
result[i] := result[i] + 1
end
end;
{ Nullify result if the utilized `prime` list was insufficient. }
if n <> 1 then
begin
{ `array` literals need an explicit data type specification. }
result := list[otherwise 0]
end;
{
In a Pascal function definition there must be _one_ assignment to the
(implicitly) declared variable bearing the same name as of the function.
This will be returned function result.
}
primeFactorization := result
end;
{
\brief returns whether a number is an n-smooth number
\param smoothness the maximum permissible prime factor
\param x the number to check
\return whether \param x is smoothness-smooth
}
function isSmooth(
protected smoothness: cardinalPositive;
protected x: natural
): Boolean;
{
Return set of non-one factors (i.e. non-zero exponent).
Nesting this function permits most compilers to allocate memory
for variables only if the function is actually needed.
}
function factorizationBases: cardinals;
var
exponent: list;
i: primeIndex;
result: cardinals value [];
begin
exponent := primeFactorization(x);
for i := 1 to primeCount do
begin
if exponent[i] > 0 then
begin
result := result + [prime[i]]
end
end;
factorizationBases := result
end;
begin
case smoothness of
1:
begin
{
The value `1` actually does not have a prime factorization, yet as per
task specification “1 (unity) is always included in n‑smooth numbers.”
}
isSmooth := x = 1
end;
{ 2‑smooth numbers is an alias for powers of 2 (OEIS sequence A000079) }
2:
begin
isSmooth := 2 pow round(ln(x) / ln(2)) = x
end
{ The `otherwise` catch-all-clause is an Extended Pascal extension. }
otherwise
begin
isSmooth := card(factorizationBases - [0..smoothness]) = 0
{
`card` (“cardinality”) is an Extended Pascal extension.
Testing `card(M) = 0` is equivalent to `M = []` (empty set).
}
end
end
end;
{ === ancillary routines =============================================== }
{ This is just your regular Eratosthenes prime sieve. }
procedure sieve(var primes: cardinals);
var
n: natural;
i: integer;
multiples: cardinals;
begin
{ `1` is by definition not a prime number }
primes := primes - [1];
{ find the next non-crossed number }
for n := 2 to cardinalMax do
begin
if n in primes then
begin
multiples := [];
{ We do _not_ want to remove 1 * n. }
i := 2 * n;
while i in [n..cardinalMax] do
begin
multiples := multiples + [i];
i := i + n
end;
primes := primes - multiples
end
end
end;
{ This procedure transforms a `set` to an `array`. }
procedure populatePrime;
var
primes: cardinals value [1..cardinalMax];
n: natural value 1;
i: primeIndex value 1;
begin
sieve(primes);
for i := 1 to primeCount do
begin
repeat
begin
n := n + 1
end
until n in primes;
prime[i] := n
end
end;
{ ### MAIN ############################################################# }
var
i: primeIndex value primeCount;
candidate: natural;
count: cardinal;
begin
populatePrime;
{ Show the first 25 n-smooth numbers […] }
{ […] only prime [n] are to be used. }
while prime[i] > 29 do
begin
i := i - 1
end;
{
In Pascal, `for` loop limits are evaluated _once_,
so this is perfectly legal:
}
for i := 1 to i do
begin
write(prime[i]:4, '-smooth: 1');
count := 1; { `1` already listed. }
candidate := 2;
while count < 25 do
begin
if isSmooth(prime[i], candidate) then
begin
write(', ', candidate:1);
count := count + 1
end;
candidate := candidate + 1
end;
writeLn
end;
{
Note, in Pascal, the `for`‑loop iteration variable is not modified.
At this point in the code, `i` (still) has the value after the `while`-loop.
[This statement is not true, if a `goto` prematurely exited the `for`‑loop.]
}
writeLn;
{ […] show three numbers starting with 3,000 […] }
for i := 2 to i do
begin
write(prime[i]:4, '-smooth:');
count := 0;
candidate := 3000;
while count < 3 do
begin
if isSmooth(prime[i], candidate) then
begin
write(' ', candidate:1);
count := count + 1
end;
candidate := candidate + 1
end;
writeLn
end;
end.</syntaxhighlight>
{{out}}
<pre style="height:45ex"> 2-smooth: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216
3-smooth: 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192
5-smooth: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54
7-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36
11-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32
13-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28
17-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27
19-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26
23-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25
29-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25
3-smooth: 3072 3456 3888
5-smooth: 3000 3072 3125
7-smooth: 3000 3024 3072
11-smooth: 3000 3024 3025
13-smooth: 3000 3003 3024
17-smooth: 3000 3003 3024
19-smooth: 3000 3003 3024
23-smooth: 3000 3003 3024
29-smooth: 3000 3003 3016</pre>
==={{header|Free Pascal}}===
misunderstood limit 3000 as n-smooth number index. So 2-smooth (3000) = 2^n was out of reach.
<syntaxhighlight lang="pascal">program HammNumb;
{$IFDEF FPC} {$MODE DELPHI} {$OPTIMIZATION ON,ALL}{$ENDIF}
{$IFDEF WINDOWS}{$APPTYPE CONSOLE}{$ENDIF}
type
tHamNum = record
hampot : array[0..167] of Word;
hampotmax,
hamNum : NativeUint;
end;
const
primes : array[0..167] of word =
(2, 3, 5, 7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71
,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151
,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233
,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317
,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419
,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503
,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607
,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701
,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811
,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911
,919,929,937,941,947,953,967,971,977,983,991,997);
var
HNum:tHamNum;
procedure OutHamNum(const HNum:tHamNum);
var
Begin
Begin
if hampot[i] = 1 then
write(primes[i],'*')
else
write(primes[i],'^',hampot[i],'*');
end;
if hampot[hampotmax] >0 then
begin
write(primes[hampotmax]);
if hampot[hampotmax] > 1 then
write('^',hampot[hampotmax]);
end;
end;
writeln;
end;
procedure NextHammNum(var HNum:tHamNum;maxP:NativeInt);
var
begin
//special case prime = 2
IF maxP = 0 then
begin
IF HNum.hampot[0] <> 0 then
HNum.hamNum *= 2
else
HNum.hamNum := 1;
inc(HNum.hampot[0]);
EXIT;
end;
n
repeat
repeat
momPrime := primes[pIdx];
q := nr div momPrime;
p := 0;
While q*momPrime=nr do
Begin
inc(p);
nr := q;
q := nr div momPrime;
end;
HNum.hampot[pIdx] := p;
inc(pIdx);
until (nr=1) OR (pIdx > maxp)
//found one, than finished
until nr = 1;
With HNum do
Begin
hamNum := n;
hamPotmax := pIdx-1;
end;
end;
procedure OutXafterYSmooth(X,Y,SmoothIdx: NativeUInt);
var
begin
fillChar(HNum,SizeOf(HNum),#0);
i := 0;
While HNum.HamNum < Y do
NextHammNum(HNum,SmoothIdx);
write('first ',X,' after ',Y,' ',primes[SmoothIdx]:3,'-smooth numbers : ');
IF x >10 then
for i := 1 to X-1 do
begin
write(HNum.HamNum,' ');
NextHammNum(HNum,SmoothIdx);
end;
writeln(HNum.HamNum,' ');
end;
var
Begin
while primes[j] < 503 do
inc(j);
while primes[j] <= 521 do
Begin
OutXafterYSmooth(20,30000,j);
OutHamNum(Hnum);
inc(j);
end;
writeln;
End.</syntaxhighlight>
{{out}}
<pre>first 25 after 1 2-smooth numbers :
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216
first 25 after 1 3-smooth numbers :
1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96 108 128 144 162 192
first 25 after 1 5-smooth numbers :
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54
first 25 after 1 7-smooth numbers :
1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36
first 25 after 1 11-smooth numbers :
1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32
first 25 after 1 13-smooth numbers :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20 21 22 24 25 26 27 28
first 25 after 1 17-smooth numbers :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 25 26 27
first 25 after 1 19-smooth numbers :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26
first 25 after 1 23-smooth numbers :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
first 25 after 1 29-smooth numbers :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
first
first
first
first 3 after 3000 11-smooth numbers : 3000 3024 3025
first 3 after 3000 13-smooth numbers : 3000 3003 3024
first 3 after 3000 17-smooth numbers : 3000 3003 3024
first 3 after 3000 19-smooth numbers : 3000 3003 3024
first 3 after 3000 23-smooth numbers : 3000 3003 3024
first 3 after 3000 29-smooth numbers : 3000 3003 3016
first 20 after 30000 503-smooth numbers :
30000 30003 30005 30008 30012 30014 30015 30016 30020 30024 30030 30033 30039 30044 30046 30048 30049 30051 30056 30057
30057 : 3*43*233
first 20 after 30000 509-smooth numbers :
30000 30003 30005 30008 30012 30014 30015 30016 30020 30024 30030 30031 30033 30039 30044 30046 30048 30049 30051 30056
30056 : 2^3*13*17^2
first 20 after 30000 521-smooth numbers :
30000 30003 30005 30008 30012 30014 30015 30016 30020 30024 30030 30031 30033 30039 30044 30046 30048 30049 30051 30056
30056 : 2^3*13*17^2</pre>
=={{header|Perl}}==
{{libheader|ntheory}}
<
use warnings;
use feature 'say';
Line 2,131 ⟶ 3,493:
} until @Sm == $cnt;
say join ' ', @Sm;
}</
{{out}}
Line 2,186 ⟶ 3,548:
{{libheader|Phix/mpfr}}
{{trans|Julia}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">nsmooth</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">needed</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- note that n is a prime index, ie 1,2,3,4... for 2,3,5,7...</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">smooth</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)},</span>
<span style="color: #000000;">nexts</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_primes</span><span style="color: #0000FF;">(-</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">indices</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> <span style="color: #000000;">nexts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nexts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">needed</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init_set</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nexts</span><span style="color: #0000FF;">))</span>
<span style="color: #000000;">smooth</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">smooth</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nexts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)<=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">indices</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nexts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span><span style="color: #000000;">smooth</span><span style="color: #0000FF;">[</span><span style="color: #000000;">indices</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]],</span><span style="color: #7060A8;">get_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">smooth</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">flat_str</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]),</span><span style="color: #000000;">ml</span><span style="color: #0000FF;">:=</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d-smooth[1..25]: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">get_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #000000;">flat_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nsmooth</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25</span><span style="color: #0000FF;">))})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d-smooth[3000..3002]: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">get_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #000000;">flat_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nsmooth</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3002</span><span style="color: #0000FF;">)[</span><span style="color: #000000;">3000</span><span style="color: #0000FF;">..</span><span style="color: #000000;">3002</span><span style="color: #0000FF;">])})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">96</span> <span style="color: #008080;">to</span> <span style="color: #000000;">98</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- primes 503, 509, and 521</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d-smooth[30000..30019]: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">get_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #000000;">flat_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nsmooth</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">30019</span><span style="color: #0000FF;">)[</span><span style="color: #000000;">30000</span><span style="color: #0000FF;">..</span><span style="color: #000000;">30019</span><span style="color: #0000FF;">])})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,250 ⟶ 3,615:
=={{header|Python}}==
{{trans|C#}}
<
def isPrime(n):
Line 2,330 ⟶ 3,695:
print
main()</
{{out}}
<pre>The first 2 -smooth numbers are:
Line 2,397 ⟶ 3,762:
The 30000 to 3019 521 -smooth numbers are:
[62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336]</pre>
=={{header|Quackery}}==
<syntaxhighlight lang="quackery">
[ behead 0 swap rot
witheach
[ 2dup < iff
drop done
nip nip
i^ 1+ swap ] ] is smallest ( [ --> n n )
[ stack ] is end.test ( --> s )
[ ]'[ end.test put
dup temp put
' [ 1 ]
0 rot size of
[ over end.test share do if done
[] unrot
dup dip
[ witheach
[ dip dup peek
temp share i^ peek *
rot swap join swap ] ]
rot smallest
dip
[ 2dup peek 1+ unrot poke ]
rot swap over
-1 peek over = iff
drop else join
swap again ]
drop
end.test release
temp release ] is smoothwith ( [ --> [ )
[ ' [ 2 3 5 7 11 13 17 19 23 29 ]
swap split drop ] is primes ( n --> [ )
10 times
[ i^ 1+ primes
smoothwith [ size 25 = ]
echo cr ]
cr
9 times
[ i^ 2 + primes
smoothwith [ size 3002 = ]
-3 split nip echo cr ]</syntaxhighlight>
{{out}}
<pre>[ 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 ]
[ 1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96 108 128 144 162 192 ]
[ 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 ]
[ 1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 ]
[ 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32 ]
[ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20 21 22 24 25 26 27 28 ]
[ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 25 26 27 ]
[ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26 ]
[ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ]
[ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ]
[ 91580367978306252441724649472 92829823186414819915547541504 94096325042746502515294076928 ]
[ 278942752080 279936000000 281250000000 ]
[ 50176000 50331648 50388480 ]
[ 2112880 2116800 2117016 ]
[ 390000 390390 390625 ]
[ 145800 145860 146016 ]
[ 74256 74358 74360 ]
[ 46552 46575 46585 ]
[ 33516 33524 33534 ]
</pre>
=={{header|Raku}}==
Line 2,402 ⟶ 3,838:
{{works with|Rakudo|2019.07.1}}
<syntaxhighlight lang="raku"
cache my \Smooth := gather {
my %i = (flat @list) Z=> (Smooth.iterator for ^@list);
Line 2,439 ⟶ 3,875:
put "\n{$start}th through {$start+19}th {@primes[$i]}-smooth numbers:\n" ~
smooth-numbers(|@primes[0..$i])[$start - 1 .. $start + 18];
}</
{{out}}
Line 2,492 ⟶ 3,928:
=={{header|REXX}}==
<
numeric digits 200 /*be able to handle some big numbers. */
parse arg LOx HIx LOn HIn . /*obtain optional arguments from the CL*/
Line 2,535 ⟶ 3,971:
end /*j*/; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
th: parse arg th; return th || word('th st nd rd', 1+(th//10)*(th//100%10\==1)*(th//10<4))</
{{out|output|text= when using the default inputs:}}
<pre>
Line 2,611 ⟶ 4,047:
=={{header|Ruby}}==
{{trans|Python}}
<
return n | 1 == 3 if n < 5 # n: 2,3|true; 0,1,4|false
return false if n.gcd(6) != 1 #
sqrtN = Integer.sqrt(n)
pc = -1 # initial P3 prime candidates value
Line 2,664 ⟶ 4,100:
print nsmooth(prime, 30019)[29999..-1] # for ruby >= 2.6: (..)[29999..]
puts
end</
{{out}}
Line 2,709 ⟶ 4,145:
=={{header|Rust}}==
{{trans|C}}
<syntaxhighlight lang="rust">fn is_prime(n: u32) -> bool {
if n < 2 {
return false;
Line 2,746 ⟶ 4,179:
}
fn find_nsmooth_numbers(n: u32, count: usize) -> Vec<
let primes = find_primes(2, n);
let num_primes = primes.len();
Line 2,755 ⟶ 4,187:
for i in 0..num_primes {
index.push(0);
queue.push
}
result.push
for i in 1..count {
for p in 0..num_primes {
if queue[p] == result[i - 1] {
index[p] += 1;
queue[p]
}
}
Line 2,771 ⟶ 4,203:
}
}
result.push(
}
result
Line 2,806 ⟶ 4,238:
}
}
}</
{{out}}
Line 2,840 ⟶ 4,272:
=={{header|Sidef}}==
<
var s = primes.len.of { [1] }
{
Line 2,862 ⟶ 4,294:
var g = smooth_generator(p.primes)
say ("3,000th through 3,002nd #{'%2d'%p}-smooth numbers: ", 3002.of { g.run }.last(3).join(' '))
}</
{{out}}
<pre>
Line 2,888 ⟶ 4,320:
Optionally, an efficient algorithm for checking if a given arbitrary large number is smooth over a given product of primes:
<
return true if (n == 1)
Line 2,905 ⟶ 4,337:
var a = {|n| is_smooth_over_prod(n, k) }.first(30_019).last(20)
say ("30,000th through 30,019th #{p}-smooth numbers: ", a.join(' '))
}</
{{out}}
<pre>
Line 2,917 ⟶ 4,349:
{{libheader|AttaSwift BigInt}}
<
import Foundation
Line 2,980 ⟶ 4,412:
for n in 503...521 where n.isPrime {
print("The 30,000...30,019 \(n)-smooth numbers are: \(smoothN(n: BigInt(n), count: 30_019).dropFirst(29999).prefix(20))")
}</
{{out}}
Line 3,013 ⟶ 4,445:
{{libheader|Wren-math}}
{{libheader|Wren-big}}
<
import "./big" for BigInt, BigInts
// cache all primes up to 521
Line 3,067 ⟶ 4,499:
System.print(nSmooth.call(i, 30019)[29999..-1])
System.print()
}</
{{out}}
Line 3,141 ⟶ 4,573:
{{trans|Go}}
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library and primes
<
fcn nSmooth(n,sz){ // --> List of big ints
Line 3,163 ⟶ 4,595:
}
ns
}</
<
p:=BI(1); while(p<29) { smallPrimes.append(p.nextPrime().toInt()) }
Line 3,178 ⟶ 4,610:
println("\nThe 30,000th to 30,019th %d-smooth numbers are:".fmt(p));
println(nSmooth(p,30019)[29999,*].concat(" "));
}</
{{out}}
<pre style="height:45ex">
|