Additive primes: Difference between revisions

From Rosetta Code
Content added Content deleted
m (Forth - simplified code)
Line 75: Line 75:
<pre>2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283
<pre>2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283
311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487</pre>
311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487</pre>
=={{header|AWK}}==
<lang AWK>
# syntax: GAWK -f ADDITIVE_PRIMES.AWK
BEGIN {
start = 1
stop = 500
for (i=start; i<=stop; i++) {
if (is_prime(i) && is_prime(sum_digits(i))) {
printf("%4d%1s",i,++count%10?"":"\n")
}
}
printf("\nAdditive primes %d-%d: %d\n",start,stop,count)
exit(0)
}
function is_prime(x, i) {
if (x <= 1) {
return(0)
}
for (i=2; i<=int(sqrt(x)); i++) {
if (x % i == 0) {
return(0)
}
}
return(1)
}
function sum_digits(n, i,sum) {
for (i=1; i<=length(n); i++) {
sum += substr(n,i,1)
}
return(sum)
}
</lang>
{{out}}
<pre>
2 3 5 7 11 23 29 41 43 47
61 67 83 89 101 113 131 137 139 151
157 173 179 191 193 197 199 223 227 229
241 263 269 281 283 311 313 317 331 337
353 359 373 379 397 401 409 421 443 449
461 463 467 487
Additive primes 1-500: 54
</pre>


=={{header|C++}}==
=={{header|C++}}==

Revision as of 14:48, 5 April 2021

Additive primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Definitions

In mathematics, additive primes are prime numbers for which the sum of their decimal digits are also primes.


Task

Write a program to determine (and show here) all additive primes less than 500.

Optionally, show the number of additive primes.


Also see



ALGOL W

<lang algolw>begin % find some additive primes - primes whose digit sum is also prime %

   % sets p( 1 :: n ) to a sieve of primes up to n %
   procedure Eratosthenes ( logical array p( * ) ; integer value n ) ;
   begin
       p( 1 ) := false; p( 2 ) := true;
       for i := 3 step 2 until n do p( i ) := true;
       for i := 4 step 2 until n do p( i ) := false;
       for i := 3 step 2 until truncate( sqrt( n ) ) do begin
           integer ii; ii := i + i;
           if p( i ) then for pr := i * i step ii until n do p( pr ) := false
       end for_i ;
   end Eratosthenes ;
   integer MAX_NUMBER;
   MAX_NUMBER := 500;
   begin
       logical array prime( 1 :: MAX_NUMBER );
       integer       aCount;
       % sieve the primes to MAX_NUMBER %
       Eratosthenes( prime, MAX_NUMBER );
       % find the primes that are additive primes %
       aCount := 0;
       for i := 1 until MAX_NUMBER - 1 do begin
           if prime( i ) then begin
               integer dSum, v;
               v    := i;
               dSum := 0;
               while v > 0 do begin
                   dSum := dSum + v rem 10;
                   v    := v div 10
               end while_v_gt_0 ;
               if prime( dSum ) then begin
                   writeon( i_w := 4, s_w := 0, " ", i );
                   aCount := aCount + 1;
                   if aCount rem 20 = 0 then write()
               end if_prime_dSum
           end if_prime_i
       end for_i ;
       write( i_w := 1, s_w := 0, "Found ", aCount, " additive primes below ", MAX_NUMBER )
   end

end.</lang>

Output:
    2    3    5    7   11   23   29   41   43   47   61   67   83   89  101  113  131  137  139  151
  157  173  179  191  193  197  199  223  227  229  241  263  269  281  283  311  313  317  331  337
  353  359  373  379  397  401  409  421  443  449  461  463  467  487
Found 54 additive primes below 500

APL

<lang APL>((+⌿(4/10)⊤P)∊P)/P←(~P∊P∘.×P)/P←1↓⍳500</lang>

Output:
2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283
      311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487

AWK

<lang AWK>

  1. syntax: GAWK -f ADDITIVE_PRIMES.AWK

BEGIN {

   start = 1
   stop = 500
   for (i=start; i<=stop; i++) {
     if (is_prime(i) && is_prime(sum_digits(i))) {
       printf("%4d%1s",i,++count%10?"":"\n")
     }
   }
   printf("\nAdditive primes %d-%d: %d\n",start,stop,count)
   exit(0)

} function is_prime(x, i) {

   if (x <= 1) {
     return(0)
   }
   for (i=2; i<=int(sqrt(x)); i++) {
     if (x % i == 0) {
       return(0)
     }
   }
   return(1)

} function sum_digits(n, i,sum) {

   for (i=1; i<=length(n); i++) {
     sum += substr(n,i,1)
   }
   return(sum)

} </lang>

Output:
   2    3    5    7   11   23   29   41   43   47
  61   67   83   89  101  113  131  137  139  151
 157  173  179  191  193  197  199  223  227  229
 241  263  269  281  283  311  313  317  331  337
 353  359  373  379  397  401  409  421  443  449
 461  463  467  487
Additive primes 1-500: 54

C++

<lang cpp>#include <iomanip>

  1. include <iostream>

bool is_prime(unsigned int n) {

   if (n < 2)
       return false;
   if (n % 2 == 0)
       return n == 2;
   if (n % 3 == 0)
       return n == 3;
   for (unsigned int p = 5; p * p <= n; p += 4) {
       if (n % p == 0)
           return false;
       p += 2;
       if (n % p == 0)
           return false;
   }
   return true;

}

unsigned int digit_sum(unsigned int n) {

   unsigned int sum = 0;
   for (; n > 0; n /= 10)
       sum += n % 10;
   return sum;

}

int main() {

   const unsigned int limit = 500;
   std::cout << "Additive primes less than " << limit << ":\n";
   unsigned int count = 0;
   for (unsigned int n = 1; n < limit; ++n) {
       if (is_prime(digit_sum(n)) && is_prime(n)) {
           std::cout << std::setw(3) << n;
           if (++count % 10 == 0)
               std::cout << '\n';
           else
               std::cout << ' ';
       }
   }
   std::cout << '\n' << count << " additive primes found.\n";

}</lang>

Output:
Additive primes less than 500:
  2   3   5   7  11  23  29  41  43  47
 61  67  83  89 101 113 131 137 139 151
157 173 179 191 193 197 199 223 227 229
241 263 269 281 283 311 313 317 331 337
353 359 373 379 397 401 409 421 443 449
461 463 467 487 
54 additive primes found.

F#

This task uses Extensible Prime Generator (F#) <lang fsharp> // Additive Primes. Nigel Galloway: March 22nd., 2021 let rec fN g=function n when n<10->n+g |n->fN(g+n%10)(n/10) primes32()|>Seq.takeWhile((>)500)|>Seq.filter(fN 0>>isPrime)|>Seq.iter(printf "%d "); printfn "" </lang>

Output:
2 3 5 7 11 23 29 41 43 47 61 67 83 89 101 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397 401 409 421 443 449 461 463 467 487

Factor

Works with: Factor version 0.99 2021-02-05

<lang factor>USING: formatting grouping io kernel math math.primes prettyprint sequences ;

sum-digits ( n -- sum )
   0 swap [ 10 /mod rot + swap ] until-zero ;

499 primes-upto [ sum-digits prime? ] filter [ 9 group simple-table. nl ] [ length "Found %d additive primes < 500.\n" printf ] bi</lang>

Output:
2   3   5   7   11  23  29  41  43
47  61  67  83  89  101 113 131 137
139 151 157 173 179 191 193 197 199
223 227 229 241 263 269 281 283 311
313 317 331 337 353 359 373 379 397
401 409 421 443 449 461 463 467 487

Found  54  additive primes  <  500.

Forth

Works with: Gforth

<lang forth>: prime? ( n -- ? ) here + c@ 0= ;

notprime! ( n -- ) here + 1 swap c! ;
prime_sieve ( n -- )
 here over erase
 0 notprime!
 1 notprime!
 2
 begin
   2dup dup * >
 while
   dup prime? if
     2dup dup * do
       i notprime!
     dup +loop
   then
   1+
 repeat
 2drop ;
digit_sum ( u -- u )
 dup 10 < if exit then
 10 /mod recurse + ;
print_additive_primes ( n -- )
 ." Additive primes less than " dup 1 .r ." :" cr
 dup prime_sieve
 0 swap
 1 do
   i prime? if
     i digit_sum prime? if
       i 3 .r
       1+ dup 10 mod 0= if cr else space then
     then
   then
 loop
 cr . ." additive primes found." cr ;

500 print_additive_primes bye</lang>

Output:
Additive primes less than 500:
  2   3   5   7  11  23  29  41  43  47
 61  67  83  89 101 113 131 137 139 151
157 173 179 191 193 197 199 223 227 229
241 263 269 281 283 311 313 317 331 337
353 359 373 379 397 401 409 421 443 449
461 463 467 487 
54 additive primes found.

Go

<lang go>package main

import "fmt"

func isPrime(n int) bool {

   switch {
   case n < 2:
       return false
   case n%2 == 0:
       return n == 2
   case n%3 == 0:
       return n == 3
   default:
       d := 5
       for d*d <= n {
           if n%d == 0 {
               return false
           }
           d += 2
           if n%d == 0 {
               return false
           }
           d += 4
       }
       return true
   }

}

func sumDigits(n int) int {

   sum := 0
   for n > 0 {
       sum += n % 10
       n /= 10
   }
   return sum

}

func main() {

   fmt.Println("Additive primes less than 500:")
   i := 2
   count := 0
   for {
       if isPrime(i) && isPrime(sumDigits(i)) {
           count++
           fmt.Printf("%3d  ", i)
           if count%10 == 0 {
               fmt.Println()
           }
       }
       if i > 2 {
           i += 2
       } else {
           i++
       }
       if i > 499 {
           break
       }
   }
   fmt.Printf("\n\n%d additive primes found.\n", count)

}</lang>

Output:
Additive primes less than 500:
  2    3    5    7   11   23   29   41   43   47  
 61   67   83   89  101  113  131  137  139  151  
157  173  179  191  193  197  199  223  227  229  
241  263  269  281  283  311  313  317  331  337  
353  359  373  379  397  401  409  421  443  449  
461  463  467  487
 
54 additive primes found.

Julia

<lang julia>using Primes

let

   p = primesmask(500)
   println("Additive primes under 500:")
   pcount = 0
   for i in 2:499
       if p[i] && p[sum(digits(i))]
           pcount += 1
           print(lpad(i, 4), pcount % 20 == 0 ? "\n" : "")
       end
   end
   println("\n\n$pcount additive primes found.")

end

</lang>

Output:
Erdős primes under 500:
   2   3   5   7  11  23  29  41  43  47  61  67  83  89 101 113 131 137 139 151
 157 173 179 191 193 197 199 223 227 229 241 263 269 281 283 311 313 317 331 337
 353 359 373 379 397 401 409 421 443 449 461 463 467 487

54 additive primes found.

Perl

Library: ntheory

<lang perl>use strict; use warnings; use ntheory 'is_prime'; use List::Util <sum max>;

sub pp {

   my $format = ('%' . (my $cw = 1+length max @_) . 'd') x @_;
   my $width  = ".{@{[$cw * int 60/$cw]}}";
   (sprintf($format, @_)) =~ s/($width)/$1\n/gr;

}

my($limit, @ap) = 500; is_prime($_) and is_prime(sum(split ,$_)) and push @ap, $_ for 1..$limit;

print @ap . " additive primes < $limit:\n" . pp(@ap);</lang>

Output:
54 additive primes < 500:
   2   3   5   7  11  23  29  41  43  47  61  67  83  89 101
 113 131 137 139 151 157 173 179 191 193 197 199 223 227 229
 241 263 269 281 283 311 313 317 331 337 353 359 373 379 397
 401 409 421 443 449 461 463 467 487

Phix

function additive(integer p) return is_prime(sum(sq_sub(sprint(p),'0'))) end function
sequence res = filter(get_primes_le(500),additive)
string r = join(shorten(apply(res,sprint),"",6))
printf(1,"%d additive primes found: %s\n",{length(res),r})
Output:
54 additive primes found: 2 3 5 7 11 23 ... 443 449 461 463 467 487

Raku

<lang perl6>unit sub MAIN ($limit = 500); say "{+$_} additive primes < $limit:\n{$_».fmt("%" ~ $limit.chars ~ "d").batch(10).join("\n")}",

   with ^$limit .grep: { .is-prime and .comb.sum.is-prime }</lang>
Output:
54 additive primes < 500:
  2   3   5   7  11  23  29  41  43  47
 61  67  83  89 101 113 131 137 139 151
157 173 179 191 193 197 199 223 227 229
241 263 269 281 283 311 313 317 331 337
353 359 373 379 397 401 409 421 443 449
461 463 467 487

REXX

<lang rexx>/*REXX program counts/displays the number of additive primes under a specified number N.*/ parse arg n cols . /*get optional number of primes to find*/ if n== | n=="," then n= 500 /*Not specified? Then assume default.*/ if cols== | cols=="," then cols= 10 /* " " " " " */ call genP n /*generate all primes under N. */ w= 10 /*width of a number in any column. */ if cols>0 then say ' index │'center(" additive primes that are < " n, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') Aprimes= 0; idx= 1 /*initialize # of additive primes & idx*/ $= /*a list of additive primes (so far). */

      do j=2  until j>=n; if \!.j  then iterate /*Is  J  not a prime? No, then skip it.*/
      _= sumDigs(j);      if \!._  then iterate /*is sum of J's digs a prime? No, skip.*/
      Aprimes= Aprimes + 1                      /*bump the count of additive primes.   */
      if cols==0            then iterate        /*Build the list  (to be shown later)? */
      c= commas(j)                              /*maybe add commas to the number.      */
      $= $ right(c, max(w, length(c) ) )        /*add additive prime──►list, allow big#*/
      if Aprimes//cols\==0  then iterate        /*have we populated a line of output?  */
      say center(idx, 7)'│'  substr($, 2);  $=  /*display what we have so far  (cols). */
      idx= idx + cols                           /*bump the  index  count for the output*/
      end   /*j*/

if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ say say 'found ' commas(Aprimes) " additive primes < " commas(n) exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? sumDigs: parse arg x 1 s 2; do k=2 for length(x)-1; s= s + substr(x,k,1); end; return s /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: parse arg n; @.=.; @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; @.7=17; #= 7

     w= length(n);  !.=0; !.2=1;  !.3=1;  !.5=1;  !.7=1;  !.11=1;  !.13=1;  !.17=1
           do j=@.7+2  by 2  while j<n          /*continue on with the next odd prime. */
           parse var  j    -1  _              /*obtain the last digit of the  J  var.*/
           if _      ==5  then iterate          /*is this integer a multiple of five?  */
           if j // 3 ==0  then iterate          /* "   "     "    "     "     " three? */
                                                /* [↓]  divide by the primes.   ___    */
                 do k=4  to #  while  k*k<=j    /*divide  J  by other primes ≤ √ J     */
                 if j//@.k == 0  then iterate j /*÷ by prev. prime?  ¬prime     ___    */
                 end   /*k*/                    /* [↑]   only divide up to     √ J     */
           #= # + 1;          @.#= j;  !.j= 1   /*bump prime count; assign prime & flag*/
           end   /*j*/
    return</lang>
output   when using the default inputs:
 index │                                        additive primes that are  <  500
───────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────
   1   │          2          3          5          7         11         23         29         41         43         47
  11   │         61         67         83         89        101        113        131        137        139        151
  21   │        157        173        179        191        193        197        199        223        227        229
  31   │        241        263        269        281        283        311        313        317        331        337
  41   │        353        359        373        379        397        401        409        421        443        449
  51   │        461        463        467        487

found  54  additive primes  <  500

Ring

<lang ring> load "stdlib.ring"

see "working..." + nl see "Additive primes are:" + nl

row = 0 limit = 500

for n = 1 to limit

   num = 0
   if isprime(n) 
      strn = string(n)
      for m = 1 to len(strn)
          num = num + number(strn[m])
      next
      if isprime(num)
         row = row + 1
         see "" + n + " "
         if row%10 = 0
            see nl
         ok
      ok
   ok

next

see nl + "found " + row + " additive primes." + nl see "done..." + nl </lang>

Output:
working...
Additive primes are:
2 3 5 7 11 23 29 41 43 47 
61 67 83 89 101 113 131 137 139 151 
157 173 179 191 193 197 199 223 227 229 
241 263 269 281 283 311 313 317 331 337 
353 359 373 379 397 401 409 421 443 449 
461 463 467 487 
found 54 additive primes.
done...

Wren

Library: Wren-math
Library: Wren-fmt

<lang ecmascript>import "/math" for Int import "/fmt" for Fmt

var sumDigits = Fn.new { |n|

   var sum = 0
   while (n > 0) {
       sum = sum + (n % 10)
       n = (n/10).floor
   }
   return sum

}

System.print("Additive primes less than 500:") var primes = Int.primeSieve(499) var count = 0 for (p in primes) {

   if (Int.isPrime(sumDigits.call(p))) {
       count = count + 1
       Fmt.write("$3d  ", p)
       if (count % 10 == 0) System.print()
   }

} System.print("\n\n%(count) additive primes found.")</lang>

Output:
Additive primes less than 500:
  2    3    5    7   11   23   29   41   43   47  
 61   67   83   89  101  113  131  137  139  151  
157  173  179  191  193  197  199  223  227  229  
241  263  269  281  283  311  313  317  331  337  
353  359  373  379  397  401  409  421  443  449  
461  463  467  487  

54 additive primes found.