Nice primes: Difference between revisions
m (Rust - minor edit) |
(Added Forth solution) |
||
Line 167: | Line 167: | ||
997 |
997 |
||
}</pre> |
}</pre> |
||
=={{header|Forth}}== |
|||
{{trans|Factor}} |
|||
{{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 ; |
|||
: digital_root ( m -- n ) 1 - 9 mod 1 + ; |
|||
: print_nice_primes ( m n -- ) |
|||
over prime_sieve |
|||
do |
|||
i prime? if |
|||
i digital_root prime? if |
|||
i . cr |
|||
then |
|||
then |
|||
loop ; |
|||
1000 500 print_nice_primes |
|||
bye</lang> |
|||
{{out}} |
|||
<pre> |
|||
509 |
|||
547 |
|||
563 |
|||
569 |
|||
587 |
|||
599 |
|||
601 |
|||
617 |
|||
619 |
|||
641 |
|||
653 |
|||
659 |
|||
673 |
|||
677 |
|||
691 |
|||
709 |
|||
727 |
|||
743 |
|||
761 |
|||
797 |
|||
821 |
|||
839 |
|||
853 |
|||
857 |
|||
887 |
|||
907 |
|||
911 |
|||
929 |
|||
941 |
|||
947 |
|||
977 |
|||
983 |
|||
997 |
|||
</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
Revision as of 15:47, 13 March 2021
- Take an positive integer n
- sumn is the sum of the decimal digits of n
- If sumn's length is greater than 1 (unity), repeat step 2 for n = sumn
- Stop when sumn's length is equal to 1 (unity)
If n and sumn are prime, then n is a Nice prime
Let 500 < n < 1000
- Example
853 (prime) 8 + 5 + 3 = 16 1 + 6 = 7 (prime)
- Also see
-
- The OEIS article: A78403 Primes such that digital root is prime.
ALGOL W
<lang algolw>begin % find some nice primes - primes whose digital root is prime %
% returns the digital root of n in base 10 % integer procedure digitalRoot( integer value n ) ; begin integer digits, sum; digits := abs n; while begin sum := 0; while digits > 0 do begin sum := sum + ( digits rem 10 ); digits := digits div 10 end % while digits > 0 % ; sum > 9 end do digits := sum; sum end digitalRoot ; % 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 MIN_PRIME, MAX_PRIME; MIN_PRIME := 501; MAX_PRIME := 999; % find the nice primes in the exclusive range 500 < prime < 1000 % begin logical array p ( 1 :: MAX_PRIME ); integer nCount; % construct a sieve of primes up to the maximum required % Eratosthenes( p, MAX_PRIME ); % show the primes that are nice % write( i_w := 1, s_w := 0, "Nice primes from ", MIN_PRIME, " to ", MAX_PRIME ); for i := MIN_PRIME until MAX_PRIME do begin if p( i ) then begin integer dr; dr := digitalRoot( i ); if p( dr ) then begin nCount := nCount + 1; write( i_w := 3, s_w := 0, nCount, ":", i, " dr(", i_w := 1, dr, ")" ) end if_dr_p end if_p_i end for_i end
end. </lang>
- Output:
Nice primes from 501 to 999 1:509 dr(5) 2:547 dr(7) 3:563 dr(5) 4:569 dr(2) 5:587 dr(2) 6:599 dr(5) 7:601 dr(7) 8:617 dr(5) 9:619 dr(7) 10:641 dr(2) 11:653 dr(5) 12:659 dr(2) 13:673 dr(7) 14:677 dr(2) 15:691 dr(7) 16:709 dr(7) 17:727 dr(7) 18:743 dr(5) 19:761 dr(5) 20:797 dr(5) 21:821 dr(2) 22:839 dr(2) 23:853 dr(7) 24:857 dr(2) 25:887 dr(5) 26:907 dr(7) 27:911 dr(2) 28:929 dr(2) 29:941 dr(5) 30:947 dr(2) 31:977 dr(5) 32:983 dr(2) 33:997 dr(7)
Factor
Using the following formula to find the digital root of a base 10 number:
- dr10(n) = 0 if n = 0,
- dr10(n) = 1 + ((n - 1) mod 9) if n ≠ 0.
(n = 0 may not need to be special-cased depending on the behavior of your language's modulo operator.)
<lang factor>USING: math math.primes prettyprint sequences ;
- digital-root ( m -- n ) 1 - 9 mod 1 + ;
500 1000 primes-between [ digital-root prime? ] filter .</lang>
- Output:
V{ 509 547 563 569 587 599 601 617 619 641 653 659 673 677 691 709 727 743 761 797 821 839 853 857 887 907 911 929 941 947 977 983 997 }
Forth
<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 ;
- digital_root ( m -- n ) 1 - 9 mod 1 + ;
- print_nice_primes ( m n -- )
over prime_sieve do i prime? if i digital_root prime? if i . cr then then loop ;
1000 500 print_nice_primes bye</lang>
- Output:
509 547 563 569 587 599 601 617 619 641 653 659 673 677 691 709 727 743 761 797 821 839 853 857 887 907 911 929 941 947 977 983 997
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("Nice primes in the interval (500, 900) are:") c := 0 for i := 501; i <= 999; i += 2 { if isPrime(i) { s := i for s >= 10 { s = sumDigits(s) } if s == 2 || s == 3 || s == 5 || s == 7 { c++ fmt.Printf("%2d: %d -> Σ = %d\n", c, i, s) } } }
}</lang>
- Output:
Same as Wren example.
Julia
See Strange_numbers#Julia for the filter_open_interval function. <lang julia>using Primes
isnice(n, base=10) = isprime(n) && (mod1(n - 1, base - 1) + 1) in [2, 3, 5, 7, 11, 13, 17, 19]
filter_open_interval(500, 1000, isnice)
</lang>
- Output:
Finding numbers matching isnice for open interval (500, 1000): 509 547 563 569 587 599 601 617 619 641 653 659 673 677 691 709 727 743 761 797 821 839 853 857 887 907 911 929 941 947 977 983 997 The total found was 33
Phix
<lang Phix>function pdr(integer n) return is_prime(n) and is_prime(1+remainder(n-1,9)) end function sequence res = filter(tagset(1000,500),pdr) printf(1,"%d nice primes found: %v\n",{length(res),shorten(res,"",5)})</lang>
- Output:
33 nice primes found: {509,547,563,569,587,"...",941,947,977,983,997}
REXX
<lang rexx>/*REXX program finds/lists triplet strange primes (<HI) where the triplets' sum is prime*/ parse arg lo hi . /*obtain optional argument from the CL.*/ if lo== | lo=="," then lo= 500 /*Not specified? Then use the default.*/ if hi== | hi=="," then hi= 1000 /* " " " " " " */ say 'list of nice primes:' /*display a title for the output list. */ call genP /*build array of semaphores for primes.*/ finds= 0 /*# of triplet strange primes (so far).*/ say
do j=lo+1 to hi-1; if \!.j then iterate /*search for nice primes within range*/ digRoot= 1 + (j - 1) // 9 /*obtain the digital root of J. */ if \!.digRoot then iterate /*Is digRoot prime? No, then skip it.*/ finds= finds + 1 /*bump the number of nice primes. */ say pad 'decimal digits of ' right(j, w) ' sum to: ' sum end /*j*/
say; @nice= ' nice primes that are between ' say 'Found ' commas(finds) @nice commas(lo) " and " commas(hi) ' (not inclusive).' 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 ? /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: !.= 0; pad= left(, 9); w= length(hi) /*placeholders for primes; width of #'s*/
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */ !.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " flags. */ #=5; s.#= @.# **2 /*number of primes so far; prime². */ /* [↓] generate more primes ≤ high.*/ do j=@.#+2 by 2 to hi /*find odd primes from here on. */ parse var j -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/ if j// 3==0 then iterate /*" " " 3? */ if j// 7==0 then iterate /*" " " 7? */ /* [↑] the above five lines saves time*/ do k=5 while s.k<=j /* [↓] divide by the known odd primes.*/ if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */ end /*k*/ /* [↑] only process numbers ≤ √ J */ #= #+1; @.#= j; s.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */ end /*j*/; return</lang>
- output when using the default inputs:
list of nice primes: decimal digits of 509 sum to: 5 decimal digits of 547 sum to: 7 decimal digits of 563 sum to: 5 decimal digits of 569 sum to: 2 decimal digits of 587 sum to: 2 decimal digits of 599 sum to: 5 decimal digits of 601 sum to: 7 decimal digits of 617 sum to: 5 decimal digits of 619 sum to: 7 decimal digits of 641 sum to: 2 decimal digits of 653 sum to: 5 decimal digits of 659 sum to: 2 decimal digits of 673 sum to: 7 decimal digits of 677 sum to: 2 decimal digits of 691 sum to: 7 decimal digits of 709 sum to: 7 decimal digits of 727 sum to: 7 decimal digits of 743 sum to: 5 decimal digits of 761 sum to: 5 decimal digits of 797 sum to: 5 decimal digits of 821 sum to: 2 decimal digits of 839 sum to: 2 decimal digits of 853 sum to: 7 decimal digits of 857 sum to: 2 decimal digits of 887 sum to: 5 decimal digits of 907 sum to: 7 decimal digits of 911 sum to: 2 decimal digits of 929 sum to: 2 decimal digits of 941 sum to: 5 decimal digits of 947 sum to: 2 decimal digits of 977 sum to: 5 decimal digits of 983 sum to: 2 decimal digits of 997 sum to: 7 Found 33 nice primes that are between 500 and 1,000 (not inclusive).
Ring
<lang ring> load "stdlib.ring"
num = 0 limit1 = 500 limit2 = 1000
see "working..." + nl see "Nice numbers are:" + nl
for n = limit1 to limit2
strn = string(n) while true sumn = 0 for m = 1 to len(strn) sumn = sumn + number(strn[m]) next if len(string(sumn)) = 1 exit ok strn = string(sumn) end if isprime(n) and isprime(sumn) num = num + 1 see "" + num + ": " + n + " > Σ = " + sumn + nl ok
next
see "done..." + nl </lang>
- Output:
working... Nice numbers are: 1: 509 > Σ = 5 2: 547 > Σ = 7 3: 563 > Σ = 5 4: 569 > Σ = 2 5: 587 > Σ = 2 6: 599 > Σ = 5 7: 601 > Σ = 7 8: 617 > Σ = 5 9: 619 > Σ = 7 10: 641 > Σ = 2 11: 653 > Σ = 5 12: 659 > Σ = 2 13: 673 > Σ = 7 14: 677 > Σ = 2 15: 691 > Σ = 7 16: 709 > Σ = 7 17: 727 > Σ = 7 18: 743 > Σ = 5 19: 761 > Σ = 5 20: 797 > Σ = 5 21: 821 > Σ = 2 22: 839 > Σ = 2 23: 853 > Σ = 7 24: 857 > Σ = 2 25: 887 > Σ = 5 26: 907 > Σ = 7 27: 911 > Σ = 2 28: 929 > Σ = 2 29: 941 > Σ = 5 30: 947 > Σ = 2 31: 977 > Σ = 5 32: 983 > Σ = 2 33: 997 > Σ = 7 done...
Rust
<lang rust>// [dependencies] // primal = "0.3"
fn digital_root(n: u64) -> u64 {
if n == 0 { 0 } else { 1 + (n - 1) % 9 }
}
fn nice_primes(from: usize, to: usize) {
primal::Sieve::new(to) .primes_from(from) .take_while(|x| *x < to) .filter(|x| primal::is_prime(digital_root(*x as u64))) .for_each(|x| println!("{}", x));
}
fn main() {
nice_primes(500, 1000);
}</lang>
- Output:
509 547 563 569 587 599 601 617 619 641 653 659 673 677 691 709 727 743 761 797 821 839 853 857 887 907 911 929 941 947 977 983 997
Wren
<lang ecmascript>import "/math" for Int import "/trait" for Stepped 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("Nice primes in the interval (500, 900) are:") var c = 0 for (i in Stepped.new(501..999, 2)) {
if (Int.isPrime(i)) { var s = i while (s >= 10) s = sumDigits.call(s) if (Int.isPrime(s)) { c = c + 1 Fmt.print("$2d: $d -> Σ = $d", c, i, s) } }
}</lang>
- Output:
Nice primes in the interval (500, 900) are: 1: 509 -> Σ = 5 2: 547 -> Σ = 7 3: 563 -> Σ = 5 4: 569 -> Σ = 2 5: 587 -> Σ = 2 6: 599 -> Σ = 5 7: 601 -> Σ = 7 8: 617 -> Σ = 5 9: 619 -> Σ = 7 10: 641 -> Σ = 2 11: 653 -> Σ = 5 12: 659 -> Σ = 2 13: 673 -> Σ = 7 14: 677 -> Σ = 2 15: 691 -> Σ = 7 16: 709 -> Σ = 7 17: 727 -> Σ = 7 18: 743 -> Σ = 5 19: 761 -> Σ = 5 20: 797 -> Σ = 5 21: 821 -> Σ = 2 22: 839 -> Σ = 2 23: 853 -> Σ = 7 24: 857 -> Σ = 2 25: 887 -> Σ = 5 26: 907 -> Σ = 7 27: 911 -> Σ = 2 28: 929 -> Σ = 2 29: 941 -> Σ = 5 30: 947 -> Σ = 2 31: 977 -> Σ = 5 32: 983 -> Σ = 2 33: 997 -> Σ = 7