Primes whose sum of digits is 25: Difference between revisions
MaiconSoft (talk | contribs) Added Delphi example |
|||
Line 161: | Line 161: | ||
load "stdlib.ring" |
load "stdlib.ring" |
||
see "working..." + nl |
|||
decimals(0) |
|||
row = 0 |
row = 0 |
||
num = 0 |
|||
nr = 0 |
|||
limit1 = 25 |
limit1 = 25 |
||
limit2 = 5000 |
limit2 = 5000 |
||
Line 177: | Line 181: | ||
ok |
ok |
||
next |
next |
||
see nl + "Found " + row + " sum25 primes below 5000" + nl |
|||
time1 = clock() |
|||
see nl |
|||
row = 0 |
|||
while true |
|||
num = num + 1 |
|||
str = string(num) |
|||
for m = 1 to len(str) |
|||
if str[m] = 0 |
|||
loop |
|||
ok |
|||
next |
|||
if isprime(num) |
|||
bool = sum25(num) |
|||
if bool = 1 |
|||
nr = nr + 1 |
|||
ok |
|||
ok |
|||
time2 = clock() |
|||
time3 = (time2-time1)/1000/60 |
|||
if time3 > 30 |
|||
exit |
|||
ok |
|||
end |
|||
see "There are " + nr + " sum25 primes that contain no zeroes" + nl |
|||
see "time = " + time3 + " mins" + nl |
|||
see "done..." + nl |
|||
func sum25(n) |
func sum25(n) |
||
Line 190: | Line 225: | ||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
working... |
|||
997 1699 1789 1879 1987 |
997 1699 1789 1879 1987 |
||
2689 2797 2887 3499 3697 |
2689 2797 2887 3499 3697 |
||
3769 3877 3967 4597 4759 |
3769 3877 3967 4597 4759 |
||
4957 4993 |
4957 4993 |
||
Found 17 sum25 primes below 5000 |
|||
There are 1555 sum25 primes that contain no zeroes |
|||
time = 30 mins |
|||
done... |
|||
</pre> |
</pre> |
Revision as of 14:47, 21 March 2021
- Task
Show primes which sum of digits is 25
Let 0 < n < 5000
- Stretch goal
Show the total number of all such primes that do not contain any zeroes (997 <= n <= 1,111,111,111,111,111,111,111,111).
ALGOL W
<lang algolw>begin % find some primes whose digits sum to 25 %
% 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 := 4999; begin logical array prime( 1 :: MAX_NUMBER ); integer pCount; % sieve the primes to MAX_NUMBER % Eratosthenes( prime, MAX_NUMBER ); % find the primes whose digits sum to 25 % pCount := 0; for i := 1 until MAX_NUMBER 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 dSum = 25 then begin writeon( i_w := 4, s_w := 0, " ", i ); pCount := pCount + 1; if pCount rem 20 = 0 then write() end if_prime_pReversed end if_prime_i end for_i ; write( i_w := 1, s_w := 0, "Found ", pCount, " sum25 primes below ", MAX_NUMBER + 1 ) end
end.</lang>
- Output:
997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993 Found 17 sum25 primes below 5000
Delphi
<lang Delphi> program Primes_which_sum_of_digits_is_25;
{$APPTYPE CONSOLE}
uses
System.SysUtils, PrimTrial;
var
row: Integer = 0; limit1: Integer = 25; limit2: Integer = 5000;
function Sum25(n: Integer): boolean; var
sum: Integer; str: string; c: char;
begin
sum := 0; str := n.ToString; for c in str do inc(sum, strToInt(c)); Result := sum = limit1;
end;
begin
for var n := 1 to limit2-1 do begin if isPrime(n) and sum25(n) then begin inc(row); write(n: 4, ' '); if (row mod 5) = 0 then writeln; end; end; readln;
end.</lang>
- Output:
997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993
Phix
<lang Phix>function sum25(integer p) return sum(sq_sub(sprint(p),'0'))=25 end function sequence res = filter(get_primes_le(5000),sum25) string r = join(shorten(apply(res,sprint),"",4)) printf(1,"%d sum25 primes less than 5000 found: %s\n",{length(res),r})</lang>
- Output:
17 sum25 primes less than 5000 found: 997 1699 1789 1879 ... 4597 4759 4957 4993
Stretch goal
<lang Phix>include mpfr.e atom t0 = time(), t1 = time()+1 mpz pz = mpz_init(0)
function sum25(string p, integer rem, res=0)
if rem=0 then if find(p[$],"1379") then -- (saves 13s) mpz_set_str(pz,p) if mpz_prime(pz) then res += 1 if time()>t1 then progress("%d, %s...",{res,p}) t1 = time()+1 end if end if end if else for i=1 to min(rem,9) do res = sum25(p&'0'+i,rem-i,res) end for end if return res
end function
printf(1,"There are %,d sum25 primes that contain no zeroes\n",sum25("",25)) ?elapsed(time()-t0)</lang>
- Output:
There are 1,525,141 sum25 primes that contain no zeroes "1 minute and 27s"
Raku
<lang perl6>unit sub MAIN ($limit = 5000); say "{+$_} primes < $limit with digital sum 25:\n{$_».fmt("%" ~ $limit.chars ~ "d").batch(10).join("\n")}",
with ^$limit .grep: { .is-prime and .comb.sum == 25 }</lang>
- Output:
17 primes < 5000 with digital sum 25: 997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993
Ring
<lang ring> load "stdlib.ring"
see "working..." + nl decimals(0) row = 0 num = 0 nr = 0 limit1 = 25 limit2 = 5000
for n = 1 to limit2
if isprime(n) bool = sum25(n) if bool = 1 row = row + 1 see "" + n + " " if (row%5) = 0 see nl ok ok ok
next
see nl + "Found " + row + " sum25 primes below 5000" + nl
time1 = clock() see nl row = 0
while true
num = num + 1 str = string(num) for m = 1 to len(str) if str[m] = 0 loop ok next if isprime(num) bool = sum25(num) if bool = 1 nr = nr + 1 ok ok time2 = clock() time3 = (time2-time1)/1000/60 if time3 > 30 exit ok
end
see "There are " + nr + " sum25 primes that contain no zeroes" + nl see "time = " + time3 + " mins" + nl see "done..." + nl
func sum25(n)
sum = 0 str = string(n) for n = 1 to len(str) sum = sum + number(str[n]) next if sum = limit1 return 1 ok
</lang>
- Output:
working... 997 1699 1789 1879 1987 2689 2797 2887 3499 3697 3769 3877 3967 4597 4759 4957 4993 Found 17 sum25 primes below 5000 There are 1555 sum25 primes that contain no zeroes time = 30 mins done...