Almost prime: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|REXX}}: optimized both REXX versions on the starting point for testing for k-almost primes. -- ~~~~)
m (→‎version 1: made the displaying of output simplier. -- ~~~~)
Line 208: Line 208:
if K=='' then K=5 /* " K? " " " " */
if K=='' then K=5 /* " K? " " " " */
/* [↓] generate one line per K.*/
/* [↓] generate one line per K.*/
do i=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=2**i until #==N /*process an almost-prime N times*/
do j=2**m until #==N /*process an almost-prime N times*/
if #factr(j)\==i then iterate /*not the correct k-almost prime?*/
if #factr(j)\==m then iterate /*not the correct k-almost prime?*/
#=#+1 /*bump the k-almost prime counter*/
#=#+1 /*bump the k-almost prime counter*/
$=$ j /*append k-almost prime to list. */
$=$ j /*append k-almost prime to list. */
end /*j*/ /* [↑] gen N k-almost primes.*/
end /*j*/ /* [↑] gen N k-almost primes.*/
say N ' ' i"-almost primes:" $ /*display the k-almost primes. */
say N right(m,4)"-almost primes:" $ /*display the k-almost primes.*/
end /*i*/ /* [↑] display a line for each K*/
end /*m*/ /* [↑] display a line for each K*/
exit /*stick a fork in it, we're done.*/
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────#FACTR subroutine───────────────────*/
/*──────────────────────────────────#FACTR subroutine───────────────────*/
Line 237: Line 237:
'''output''' when using the default input:
'''output''' when using the default input:
<pre>
<pre>
10 1-almost primes: 2 3 5 7 11 13 17 19 23 29
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 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 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 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
10 5-almost primes: 32 48 72 80 108 112 120 162 168 176
</pre>
</pre>


Revision as of 01:31, 24 February 2014

Task
Almost prime
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:

  1. Generate 10 primes.
  2. Multiply each of them by the first ten primes
  3. Sort and find unique values, take the first ten of those
  4. Multiply each of them by the first ten primes
  5. 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

Translation of: C

<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 m=1  for  K;   $=              /*generate  K   k-almost primes. */
    #=0                               /*number of k-almost primes found*/
        do j=2**m  until #==N         /*process an almost-prime N times*/
        if #factr(j)\==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 right(m,4)"-almost primes:" $ /*display the  k-almost primes.*/
    end       /*m*/                   /* [↑]  display a line for each K*/

exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────#FACTR subroutine───────────────────*/

  1. 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───────────────────*/

  1. 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
Translation of: J

<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

Works with: Tcl version 8.6
Library: Tcllib (Package: math::numtheory)

<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
Retrieved from "https://rosettacode.org/wiki/Almost_prime?oldid=240485"