Almost prime: Difference between revisions

Content added Content deleted

Inline

@@ Line 4,772: / Line 4,772: @@
 =={{header|Sidef}}==
+Efficient algorithm for generating all the k-almost prime numbers in a given range '''[a,b]''':
-{{trans|Raku}}
-<syntaxhighlight lang="ruby">func is_k_almost_prime(n, k) {
+<syntaxhighlight lang="ruby">func almost_primes(a, b, k) {
-    for (var (p, f) = (2, 0); (f < k) && (p*p <= n); ++p) {
-        (n /= p; ++f) while (p `divides` n)
+    a = max(2**k, a)
-    }
+    var arr = []
-    n > 1 ? (f.inc == k) : (f == k)
+    func (m, lo, k) {
+        var hi = idiv(b,m).iroot(k)
+        if (k == 1) {
+            lo = max(lo, idiv_ceil(a, m))
+            each_prime(lo, hi, {|p|
+                arr << m*p
+            })
+            return nil
+        }
+        each_prime(lo, hi, {|p|
+            var t = m*p
+            var u = idiv_ceil(a, t)
+            var v = idiv(b, t)
+            next if (u > v)
+            __FUNC__(t, p, k-1)
+        })
+    }(1, 2, k)
+    return arr.sort
 }
+for k in (1..5) {
-{ |k|
-    var x = 10
+    var (x=10, lo=1, hi=2)
-    say gather {
+    var arr = []
-        { |i|
+    loop {
-            if (is_k_almost_prime(i, k)) {
+        arr += almost_primes(lo, hi, k)
-                take(i)
+        break if (arr.len >= x)
-                --x == 0 && break
+        lo = hi+1
-            }
+        hi = 2*lo
-        } << 1..Inf
     }
+    say arr.first(x)
-} << 1..5</syntaxhighlight>
+}</syntaxhighlight>
 {{out}}
 <pre>
@@ Line 4,799: / Line 4,827: @@
 [32, 48, 72, 80, 108, 112, 120, 162, 168, 176]
 </pre>
+Also built-in:
+<syntaxhighlight lang="ruby">for k in (1..5) {
+    var x = 10
+    say k.almost_primes(x.nth_almost_prime(k))
+}</syntaxhighlight>
+(same output as above)
 =={{header|Swift}}==