Almost prime: Difference between revisions
(→{{header|Perl 6}}: specify method of inclusion as requested) |
m (→{{header|REXX}}: optimized both REXX versions on the starting point for testing for k-almost primes. -- ~~~~) |
||
Line 210: | Line 210: | ||
do i=1 for K; $= /*generate K k-almost primes. */ |
do i=1 for K; $= /*generate K k-almost primes. */ |
||
#=0 /*number of k-almost primes found*/ |
#=0 /*number of k-almost primes found*/ |
||
do j= |
do j=2**i until #==N /*process an almost-prime N times*/ |
||
if #factr(j)\==i then iterate /*not the correct k-almost prime?*/ |
if #factr(j)\==i then iterate /*not the correct k-almost prime?*/ |
||
#=#+1 /*bump the k-almost prime counter*/ |
#=#+1 /*bump the k-almost prime counter*/ |
||
Line 253: | Line 253: | ||
do m=1 for K; $= /*generate K k-almost primes. */ |
do m=1 for K; $= /*generate K k-almost primes. */ |
||
#=0 /*number of k-almost primes found*/ |
#=0 /*number of k-almost primes found*/ |
||
do j= |
do j=2**i until #==N /*process an almost-prime N times*/ |
||
if #factL(j,m)\==m then iterate /*not the correct k-almost prime?*/ |
if #factL(j,m)\==m then iterate /*not the correct k-almost prime?*/ |
||
#=#+1 /*bump the k-almost prime counter*/ |
#=#+1 /*bump the k-almost prime counter*/ |
Revision as of 01:11, 24 February 2014
You are encouraged to solve this task according to the task description, using any language you may know.
A k-Almost-prime is a natural number that is the product of (possibly identical) primes.
So, for example, 1-almost-primes, where , are the prime numbers themselves; 2-almost-primes are the semiprimes.
The task is to write a function/method/subroutine/... that generates k-almost primes and use it to create a table here of the first ten members of k-Almost primes for .
- Cf.
C
<lang c>#include <stdio.h>
int kprime(int n, int k) { int p, f = 0; for (p = 2; f < k && p*p <= n; p++) while (0 == n % p) n /= p, f++;
return f + (n > 1) == k; }
int main(void) { int i, c, k;
for (k = 1; k <= 5; k++) { printf("k = %d:", k);
for (i = 2, c = 0; c < 10; i++) if (kprime(i, k)) { printf(" %d", i); c++; }
putchar('\n'); }
return 0; }</lang>
- Output:
k = 1: 2 3 5 7 11 13 17 19 23 29 k = 2: 4 6 9 10 14 15 21 22 25 26 k = 3: 8 12 18 20 27 28 30 42 44 45 k = 4: 16 24 36 40 54 56 60 81 84 88 k = 5: 32 48 72 80 108 112 120 162 168 176
J
<lang J> (10 {. [:~.[:/:~[:,*/~)^:(i.5)~p:i.10
2 3 5 7 11 13 17 19 23 29 4 6 9 10 14 15 21 22 25 26 8 12 18 20 27 28 30 42 44 45
16 24 36 40 54 56 60 81 84 88 32 48 72 80 108 112 120 162 168 176</lang>
Explanation:
- Generate 10 primes.
- Multiply each of them by the first ten primes
- Sort and find unique values, take the first ten of those
- Multiply each of them by the first ten primes
- Sort and find unique values, take the first ten of those
- ...
The results of the odd steps in this procedure are the desired result.
Perl
<lang perl>use strict; use warnings;
sub k_almost_prime;
for my $k ( 1 .. 5 ) { my $almost = 0; print join(", ", map { 1 until k_almost_prime ++$almost, $k; "$almost"; } 1 .. 10), "\n"; }
sub nth_prime;
sub k_almost_prime { my ($n, $k) = @_; return if $n <= 1 or $k < 1; my $which_prime = 0; for my $count ( 1 .. $k ) { while( $n % nth_prime $which_prime ) { ++$which_prime; } $n /= nth_prime $which_prime; return if $n == 1 and $count != $k; } ($n == 1) ? 1 : (); }
BEGIN { # This is loosely based on one of the python solutions # to the RC Sieve of Eratosthenes task. my @primes = (2, 3, 5, 7); my $p_iter = 1; my $p = $primes[$p_iter]; my $q = $p*$p; my %sieve; my $candidate = $primes[-1] + 2; sub nth_prime { my $n = shift; return if $n < 0; OUTER: while( $#primes < $n ) { while( my $s = delete $sieve{$candidate} ) { my $next = $s + $candidate; $next += $s while exists $sieve{$next}; $sieve{$next} = $s; $candidate += 2; } while( $candidate < $q ) { push @primes, $candidate; $candidate += 2; next OUTER if exists $sieve{$candidate}; } my $twop = 2 * $p; my $next = $q + $twop; $next += $twop while exists $sieve{$next}; $sieve{$next} = $twop; $p = $primes[++$p_iter]; $q = $p * $p; $candidate += 2; } return $primes[$n]; } } </lang>
- Output:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29 4, 6, 9, 10, 14, 15, 21, 22, 25, 26 8, 12, 18, 20, 27, 28, 30, 42, 44, 45 16, 24, 36, 40, 54, 56, 60, 81, 84, 88 32, 48, 72, 80, 108, 112, 120, 162, 168, 176
Perl 6
<lang perl6>sub is-k-almost-prime($n is copy, $k) returns Bool {
loop (my ($p, $f) = 2, 0; $f < $k && $p*$p <= $n; $p++) { $n /= $p and $f++ while $n %% $p; } $f + ($n > 1) == $k;
}
for 1 .. 5 -> $k {
say .[^10] given grep { is-k-almost-prime($_, $k) }, 2 .. *
}</lang>
- Output:
2 3 5 7 11 13 17 19 23 29 4 6 9 10 14 15 21 22 25 26 8 12 18 20 27 28 30 42 44 45 16 24 36 40 54 56 60 81 84 88 32 48 72 80 108 112 120 162 168 176
Here is a solution with identical output based on the factors routine from Count_in_factors#Perl_6 (to be included manually until we decide where in the distribution to put it). <lang perl6>constant factory = 0..* Z=> (0, 0, map { +factors($_) }, 2..*);
sub almost($n) { map *.key, grep *.value == $n, factory }
say almost($_)[^10] for 1..5;</lang>
Python
This imports Prime decomposition#Python
<lang python>from prime_decomposition import decompose from itertools import islice, count try:
from functools import reduce
except:
pass
def almostprime(n, k=2):
d = decompose(n) try: terms = [d.next() for i in range(k)] return reduce(int.__mul__, terms, 1) == n except: return False
if __name__ == '__main__':
for k in range(1,6): print('%i: %r' % (k, list(islice((n for n in count() if almostprime(n, k)), 10))))</lang>
- Output:
1: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] 2: [4, 6, 9, 10, 14, 15, 21, 22, 25, 26] 3: [8, 12, 18, 20, 27, 28, 30, 42, 44, 45] 4: [16, 24, 36, 40, 54, 56, 60, 81, 84, 88] 5: [32, 48, 72, 80, 108, 112, 120, 162, 168, 176]
REXX
version 1
The method used is to count the number of factors in the number to determine the K-primality. <lang rexx>/*REXX program displays the N numbers of the first K k-almost primes*/ parse arg N K . /*get the arguments from the C.L.*/ if N== then N=10 /*No N? Then use the default.*/ if K== then K=5 /* " K? " " " " */
/* [↓] generate one line per K.*/ do i=1 for K; $= /*generate K k-almost primes. */ #=0 /*number of k-almost primes found*/ do j=2**i until #==N /*process an almost-prime N times*/ if #factr(j)\==i then iterate /*not the correct k-almost prime?*/ #=#+1 /*bump the k-almost prime counter*/ $=$ j /*append k-almost prime to list. */ end /*j*/ /* [↑] gen N k-almost primes.*/ say N ' ' i"-almost primes:" $ /*display the k-almost primes. */ end /*i*/ /* [↑] display a line for each K*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────#FACTR subroutine───────────────────*/
- factr: procedure;parse arg x 1 z; f=0 /*defines X and Z to the arg.*/
if x<2 then return 0 /*invalid number? Then return 0.*/
do j=2 to 5; if j\==4 then call .#factr; end /*fast factoring.*/
j=5 /*start were we left off (J=5). */
do y=0 by 2; j=j+2 + y//4 /*insure it's not divisible by 3.*/ if right(j,1)==5 then iterate /*fast check for divisible by 5.*/ if j>z then leave /*number reduced to a wee number?*/ call .#factr /*go add other factors to count. */ end /*y*/ /* [↑] find all factors in X. */
return max(f,1) /*if prime (f==0), then return 1.*/ /*──────────────────────────────────.#FACTR subroutine──────────────────*/ .#factr: do f=f+1 while z//j==0 /*keep dividing until we can't. */
z=z%j /*perform an (%) integer divide.*/ end /*while*/ /* [↑] whittle down the Z num.*/
f=f-1 /*adjust the count of factors. */ return</lang> output when using the default input:
10 1-almost primes: 2 3 5 7 11 13 17 19 23 29 10 2-almost primes: 4 6 9 10 14 15 21 22 25 26 10 3-almost primes: 8 12 18 20 27 28 30 42 44 45 10 4-almost primes: 16 24 36 40 54 56 60 81 84 88 10 5-almost primes: 32 48 72 80 108 112 120 162 168 176
version 2
The method used is practically identical to version 1, but the factoring stops if the number of factors exceeds the goal. <lang rexx>/*REXX program displays the N numbers of the first K k-almost primes*/ parse arg N K . /*get the arguments from the C.L.*/ if N== then N=10 /*No N? Then use the default.*/ if K== then K=5 /* " K? " " " " */
/* [↓] generate one line per K.*/ do m=1 for K; $= /*generate K k-almost primes. */ #=0 /*number of k-almost primes found*/ do j=2**i until #==N /*process an almost-prime N times*/ if #factL(j,m)\==m then iterate /*not the correct k-almost prime?*/ #=#+1 /*bump the k-almost prime counter*/ $=$ j /*append k-almost prime to list. */ end /*j*/ /* [↑] gen N k-almost primes.*/ say N ' ' m"-almost primes:" $ /*display the k-almost primes. */ end /*m*/ /* [↑] display a line for each K*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────#FACTL subroutine───────────────────*/
- factL: procedure; parse arg x 1 z,L /*defines X and Z to the arg.*/
f=0; if x<2 then return 0 /*invalid number? Then return 0.*/
do j=2 to 5; if j\==4 then call .#factL; end /*fast factoring.*/
if f>L then return f /*#factors > L ? Then too many.*/ j=5 /*start were we left off (J=5). */
do y=0 by 2; j=j+2 + y//4 /*insure it's not divisible by 3.*/ if right(j,1)==5 then iterate /*fast check for divisible by 5.*/ if j>z then leave /*number reduced to a wee number?*/ call .#factL /*go add other factors to count. */ if f>L then return f /*#factors > L ? Then too many.*/ end /*y*/ /* [↑] find all factors in X. */
return max(f,1) /*if prime (f==0), then return 1.*/ /*──────────────────────────────────.#FACTL subroutine──────────────────*/ .#factL: do f=f+1 while z//j==0 /*keep dividing until we can't. */
z=z%j /*perform an (%) integer divide.*/ end /*while*/ /* [↑] whittle down the Z num.*/
f=f-1 /*adjust the count of factors. */
return</lang>
output is identical to version 1.
Ruby
<lang ruby> require 'prime'
def almost_primes(k=2)
return to_enum(:almost_primes, k) unless block_given? n = 0 loop do n += 1 yield n if n.prime_division.map( &:last ).inject( &:+ ) == k end
end
(1..5).each{|k| puts almost_primes(k).take(10).join(", ")} </lang>
- Output:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29 4, 6, 9, 10, 14, 15, 21, 22, 25, 26 8, 12, 18, 20, 27, 28, 30, 42, 44, 45 16, 24, 36, 40, 54, 56, 60, 81, 84, 88 32, 48, 72, 80, 108, 112, 120, 162, 168, 176
<lang ruby>require 'prime'
p ar = pr = Prime.take(10) 4.times{p ar = ar.product(pr).map{|(a,b)| a*b}.uniq.sort.take(10)} </lang>
- Output:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29] [4, 6, 9, 10, 14, 15, 21, 22, 25, 26] [8, 12, 18, 20, 27, 28, 30, 42, 44, 45] [16, 24, 36, 40, 54, 56, 60, 81, 84, 88] [32, 48, 72, 80, 108, 112, 120, 162, 168, 176]
Tcl
<lang tcl>package require Tcl 8.6 package require math::numtheory
proc firstNprimes n {
for {set result {};set i 2} {[llength $result] < $n} {incr i} {
if {[::math::numtheory::isprime $i]} { lappend result $i }
} return $result
}
proc firstN_KalmostPrimes {n k} {
set p [firstNprimes $n] set i [lrepeat $k 0] set c {}
while true {
dict set c [::tcl::mathop::* {*}[lmap j $i {lindex $p $j}]] "" for {set x 0} {$x < $k} {incr x} { lset i $x [set xx [expr {([lindex $i $x] + 1) % $n}]] if {$xx} break } if {$x == $k} break
} return [lrange [lsort -integer [dict keys $c]] 0 [expr {$n - 1}]]
}
for {set K 1} {$K <= 5} {incr K} {
puts "$K => [firstN_KalmostPrimes 10 $K]"
}</lang>
- Output:
1 => 2 3 5 7 11 13 17 19 23 29 2 => 4 6 9 10 14 15 21 22 25 26 3 => 8 12 18 20 27 28 30 42 44 45 4 => 16 24 36 40 54 56 60 81 84 88 5 => 32 48 72 80 108 112 120 162 168 176