Primes whose first and last number is 3
Find primes n (in base ten) whose first and last decimal digit is 3, and where n < 4,000.
- Task
Show all output here on this page.
- Stretch goal
Find and show only the number of these types of primes that are < 1,000,000.
11l
F is_prime(n)
I n == 2
R 1B
I n < 2 | n % 2 == 0
R 0B
L(i) (3 .. Int(sqrt(n))).step(2)
I n % i == 0
R 0B
R 1B
V lim = 1'000'000
V primes3x3 = [3]
V m = 100
V count = 1
L m * 3 < lim
L(n) (3 * m + 3 .. 4 * m - 7).step(10)
I n > lim
L.break
I is_prime(n)
count++
I n < 4000
primes3x3.append(n)
m *= 10
print(‘Found ’primes3x3.len‘ primes starting and ending with 3 below 4000:’)
L(n) primes3x3
print(‘#4’.format(n), end' I (L.index + 1) % 11 == 0 {"\n"} E ‘ ’)
print("\nFound "count‘ primes starting and ending with 3 below 1000000.’)
- Output:
Found 33 primes starting and ending with 3 below 4000: 3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 Found 2251 primes starting and ending with 3 below 1000000.
Action!
INCLUDE "H6:SIEVE.ACT"
BYTE Func IsSpecialPrime(INT i BYTE ARRAY primes)
BYTE d,first
IF primes(i)=0 THEN
RETURN (0)
FI
first=1
WHILE i#0
DO
d=i MOD 10
IF first THEN
IF d#3 THEN
RETURN (0)
FI
first=0
FI
i==/10
OD
IF d#3 THEN
RETURN (0)
FI
RETURN (1)
PROC Main()
DEFINE MAX="3999"
BYTE ARRAY primes(MAX+1)
INT i,count=[0]
Put(125) PutE() ;clear the screen
Sieve(primes,MAX+1)
FOR i=2 TO MAX
DO
IF IsSpecialPrime(i,primes) THEN
PrintI(i) Put(32)
count==+1
FI
OD
PrintF("%E%EThere are %I primes",count)
RETURN
- Output:
Screenshot from Atari 8-bit computer
3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 There are 33 primes
ALGOL 68
With added stretch goal. As with the Go and other samples, generates the candidate sequence.
BEGIN # find some primes whose first and last digits are 3 #
INT max prime = 1 000 000; # largest number to consider #
# sieve the primes to max prime #
PR read "primes.incl.a68" PR
[]BOOL prime = PRIMESIEVE max prime;
INT p3count := 0;
# prints n, if it is prime, handles newlines #
PROC p = ( INT n )VOID:
IF prime[ n ] THEN
print( ( " ", whole( n, - 4 ) ) );
IF ( p3count +:= 1 ) MOD 12 = 0 THEN print( ( newline ) ) FI
FI # p #;
# find 3x3 primes #
p( 3 ); p( 33 ); # a & 2 digit 3x3 primes #
FOR i FROM 0 BY 10 TO 90 DO p( 303 + i ) OD; # 3 digit 3x3 primes #
FOR i FROM 0 BY 10 TO 990 DO p( 3003 + i ) OD; # 4 digit 3x3 primes #
# 5 and 6 digit 3x3 primes #
FOR i FROM 0 BY 10 TO 9 990 DO IF prime[ 30 003 + i ] THEN p3count +:= 1 FI OD;
FOR i FROM 0 BY 10 TO 99 990 DO IF prime[ 300 003 + i ] THEN p3count +:= 1 FI OD;
print( ( newline, "Found ", whole( p3count, 0 ), " ""3x3"" primes below 1000000", newline ) )
END
- Output:
3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 Found 2251 "3x3" primes below 1000000
ALGOL W
As with the Go and oher samples, finds the numbers by generating the candidate seuence.
begin % find some primes whose first and last digits are 3 %
integer MAX_PRIME;
MAX_PRIME := 4000;
begin
logical array isPrime ( 1 :: MAX_PRIME );
integer p3Count;
% increments n by 1 %
integer procedure inc( integer value result n ) ; begin n := n + 1; n end;
% prints n, if it is prime, handles newlines %
procedure p ( integer value n ) ;
if isPrime( n ) then begin writeon( i_w := 4, s_w := 0, " ", n ); if inc( p3Count ) rem 12 = 0 then write() end;
% sieve the primes to MAX_PRIME %
isPrime( 1 ) := false; isPrime( 2 ) := true;
for i := 3 step 2 until MAX_PRIME do isPrime( i ) := true;
for i := 4 step 2 until MAX_PRIME do isPrime( i ) := false;
for i := 3 step 2 until truncate( sqrt( MAX_PRIME ) ) do begin
integer ii; ii := i + i;
if isPrime( i ) then for pr := i * i step ii until MAX_PRIME do isPrime( pr ) := false
end for_i ;
% find the 3x3 primes %
p3Count := 0;
% 1, 2 and 3 digit 3x3 primes %
p( 3 ); p( 33 ); for i := 0 step 10 until 90 do p( 303 + i );
% 4 digit 3x3 primes %
for i := 0 step 10 until 990 do p( 3003 + i );
end
end.
- Output:
3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943
Arturo
firstAndLastIs3?: function [n][
if not? prime? n -> return false
return and? -> 3 = first digits n
-> 3 = last digits n
]
primesWithFirstAndLast3: select 1..4000 => firstAndLastIs3?
loop split.every: 11 primesWithFirstAndLast3 'x ->
print map x 's -> pad to :string s 5
nofPrimesBelow1M: enumerate 1..1000000 => firstAndLastIs3?
print ""
print ["Found" nofPrimesBelow1M "primes starting and ending with 3 below 1000000."]
- Output:
3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 Found 2251 primes starting and ending with 3 below 1000000.
AWK
# syntax: GAWK -f PRIMES_WHOSE_FIRST_AND_LAST_NUMBER_IS_3.AWK
BEGIN {
start = 1
stop = 3999
for (i=start; i<=stop; i++) {
if (is_prime(i) && i ~ /^3/ && i ~ /3$/) {
printf("%5d%1s",i,++count1%10?"":"\n")
}
}
printf("\nPrimes beginning and ending with '3' %d-%d: %d\n",start,stop,count1)
start = 1
stop = 999999
for (i=start; i<=stop; i++) {
if (is_prime(i) && i ~ /^3/ && i ~ /3$/) {
count2++
}
}
printf("Primes beginning and ending with '3' %d-%d: %d\n",start,stop,count2)
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)
}
- Output:
3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 Primes beginning and ending with '3' 1-3999: 33 Primes beginning and ending with '3' 1-999999: 2251
C
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int isprime( int p ) {
int i;
if(p==2) return 1;
if(!(p%2)) return 0;
for(i=3; i*i<=p; i+=2) {
if(!(p%i)) return 0;
}
return 1;
}
int main(void) {
int np = 1, d, i, n;
printf( "3 " );
for(d=1; d<6; d++) {
for(i=3; i<pow(10,d)-1; i+=10) {
n = i + 3*pow(10,d);
if(isprime(n)) {
++np;
if(n<4009) {
printf("%d ",n);
if(!(np%10)) printf("\n");
}
}
}
}
printf( "\n\nThere were %d primes of the form 3x3 below one million.\n", np );
return 0;
}
- Output:
3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943
There were 2251 primes of the form 3x3 below one million.
Delphi
function IsPrime(N: int64): boolean;
{Fast, optimised prime test}
var I,Stop: int64;
begin
if (N = 2) or (N=3) then Result:=true
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false
else
begin
I:=5;
Stop:=Trunc(sqrt(N+0.0));
Result:=False;
while I<=Stop do
begin
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit;
Inc(I,6);
end;
Result:=True;
end;
end;
procedure GetDigits(N: integer; var IA: TIntegerDynArray);
{Get an array of the integers in a number}
var T: integer;
begin
SetLength(IA,0);
repeat
begin
T:=N mod 10;
N:=N div 10;
SetLength(IA,Length(IA)+1);
IA[High(IA)]:=T;
end
until N<1;
end;
procedure ShowFirstLast3Prime(Memo: TMemo);
var I,Cnt1,Cnt2: integer;
var IA: TIntegerDynArray;
var S: string;
function FirstLast3(N: integer): boolean;
var I: integer;
begin
GetDigits(N,IA);
Result:=(IA[0]=3) and (IA[High(IA)]=3);
end;
begin
Cnt1:=0; Cnt2:=0;
S:='';
for I:=0 to 1000000-1 do
if IsPrime(I) then
if FirstLast3(I) then
begin
Inc(Cnt1);
if I<4000 then
begin
Inc(Cnt2);
S:=S+Format('%5D',[I]);
If (Cnt2 mod 5)=0 then S:=S+CRLF;
end;
end;
Memo.Lines.Add(S);
Memo.Lines.Add('Count < 1,000 = '+IntToStr(Cnt2));
Memo.Lines.Add('Count < 1,000,000 = '+IntToStr(Cnt1));
end;
- Output:
3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 Count < 1,000 = 33 Count < 1,000,000 = 2251 Elapsed Time: 181.797 ms.
EasyLang
fastfunc isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
fastfunc nextprim prim .
repeat
prim += 1
until isprim prim = 1
.
return prim
.
func digok n .
f = n mod 10
while n > 0
l = n mod 10
n = n div 10
.
return if f = 3 and l = 3
.
p = 2
repeat
if digok p = 1
write p & " "
.
p = nextprim p
until p >= 4000
.
- Output:
3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943
F#
This task uses Extensible Prime Generator (F#)
//3 Sandwich Primes. Nigel Galloway: July 25th., 2021
primes32()|>Seq.takeWhile((>)4000)|>Seq.filter(fun n->n%10=3 && (n=3||(n>29 && n<40)||(n>299 && n<400)||n>2999))|>Seq.iter(printf "%d "); printfn ""
- Output:
3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943
Factor
USING: formatting grouping io kernel lists lists.lazy math
math.functions math.primes sequences ;
: under ( list n -- list' ) '[ _ < ] lwhile ;
: (surrounded) ( n -- list )
[ 1list 1 lfrom ] keep dup dup
'[ 10^ _ * _ + [ [ 10 + ] lfrom-by ] keep dup _ / + 10 - under ]
lmap-lazy lconcat lappend-lazy ;
: surrounded ( n upto -- list )
[ (surrounded) ] [ under ] bi* [ prime? ] lfilter ;
: surrounded. ( n -- )
dup "Primes under 10,000 beginning and ending with %d:\n" printf
10,000 surrounded list>array 10 group
[ [ "%6d" printf ] each nl ] each nl ;
{ 1 3 5 7 9 } [ surrounded. ] each
3 1,000,000 surrounded llength
"Found %d primes beginning and ending with 3 under 1,000,000.\n" printf
- Output:
Primes under 10,000 beginning and ending with 1: 11 101 131 151 181 191 1021 1031 1051 1061 1091 1151 1171 1181 1201 1231 1291 1301 1321 1361 1381 1451 1471 1481 1511 1531 1571 1601 1621 1721 1741 1801 1811 1831 1861 1871 1901 1931 1951 Primes under 10,000 beginning and ending with 3: 3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 Primes under 10,000 beginning and ending with 5: 5 Primes under 10,000 beginning and ending with 7: 7 727 757 787 797 7027 7057 7127 7177 7187 7207 7237 7247 7297 7307 7417 7457 7477 7487 7507 7517 7537 7547 7577 7607 7687 7717 7727 7757 7817 7867 7877 7907 7927 7937 Primes under 10,000 beginning and ending with 9: 919 929 9029 9049 9059 9109 9199 9209 9239 9319 9349 9419 9439 9479 9539 9619 9629 9649 9679 9689 9719 9739 9749 9769 9829 9839 9859 9929 9949 Found 2251 primes beginning and ending with 3 under 1,000,000.
Fermat
np := 1;
!(3,' ');
for d = 1 to 5 do
for i = 3 to 10^d-1 by 10 do
n:=3*10^d + i;
if Isprime(n) = 1 then
np:=np+1;
if n<4000 then
!(n,' ');
if Divides(10,np) then !! fi;
fi;
fi;
od;
od;
!!;
!!;
!!('There were ',np,' primes of the form 3...3 below 1,000,000');
- Output:
3 313 353 373 383 3023 3083 3163 3203 3253
3313 3323 3343 3373 3413 3433 3463 3533 3583 3593
3613 3623 3643 3673 3733 3793 3803 3823 3833 3853
3863 3923 3943
There were 2251 primes of the form 3...3 below 1,000,000
FreeBASIC
#include "isprime.bas"
dim as integer np = 1, d, n, i
print 3;" "; 'three counts, but is a special case
for d = 1 to 5 'how many digits after the initial 3
for i = 3 to 10^d-1 step 10 'the actual digits
n = 3*10^d + i
if isprime(n) then
np += 1
if n<4000 then
print n;" ";
if np mod 10 = 0 then print
end if
end if
next i
next d
print : print
print "There were ";np;" 3...3 primes below 1000000"
- Output:
3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943There were 2251 3...3 primes below 1000000
Go
package main
import (
"fmt"
"rcu"
)
func main() {
var primes []int
candidates := []int{3, 33}
for i := 303; i <= 393; i += 10 {
candidates = append(candidates, i)
}
for i := 3003; i <= 3993; i += 10 {
candidates = append(candidates, i)
}
for _, cand := range candidates {
if rcu.IsPrime(cand) {
primes = append(primes, cand)
}
}
fmt.Println("Primes under 4,000 which begin and end in 3:")
for i, p := range primes {
fmt.Printf("%5s ", rcu.Commatize(p))
if (i+1)%11 == 0 {
fmt.Println()
}
}
fmt.Println("\nFound", len(primes), "Such primes.")
pc := len(primes)
for i := 30003; i <= 39993; i += 10 {
if rcu.IsPrime(i) {
pc++
}
}
for i := 300003; i <= 399993; i += 10 {
if rcu.IsPrime(i) {
pc++
}
}
pcc := rcu.Commatize(pc)
fmt.Println("\nFound", pcc, "primes under 1,000,000 which begin and end with 3.")
}
- Output:
Primes under 4,000 which begin and end in 3: 3 313 353 373 383 3,023 3,083 3,163 3,203 3,253 3,313 3,323 3,343 3,373 3,413 3,433 3,463 3,533 3,583 3,593 3,613 3,623 3,643 3,673 3,733 3,793 3,803 3,823 3,833 3,853 3,863 3,923 3,943 Found 33 Such primes. Found 2,251 primes under 1,000,000 which begin and end with 3.
Haskell
isPrime :: Int -> Bool
isPrime n
|n == 2 = True
|n == 1 = False
|otherwise = null $ filter (\i -> mod n i == 0 ) [2 .. root]
where
root :: Int
root = floor $ sqrt $ fromIntegral n
condition :: Int -> Bool
condition n = isPrime n && head numstr == '3' && last numstr == '3'
where
numstr :: String
numstr = show n
solution :: [Int]
solution = filter condition [1..3999]
main :: IO ( )
main = do
print solution
putStrLn ( "There are " ++ ( show $ length $ filter condition [1..999999]
) ++ " 3 x 3 primes below 1000000!" )
- Output:
[3,313,353,373,383,3023,3083,3163,3203,3253,3313,3323,3343,3373,3413,3433,3463,3533,3583,3593,3613,3623,3643,3673,3733,3793,3803,3823,3833,3853,3863,3923,3943] There are 2251 3 x 3 primes below 1000000!
J
primes3x3=. 3 ;@; 10 <@(#~ 1&p:)@(30&* + 3 + 10 * i.)@^ i.
primes3x3 3
3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943
# primes3x3 5
2251
jq
Works with gojq, the Go implementation of jq
See e.g. Erdős-primes#jq for a suitable implementation of `is_prime`.
# For the stretch goal:
def count(s): reduce s as $x (null; .+1);
# $n is the max number of intervening digits
def task($n):
3,
(range(1; $n+1) as $power
| (3 * pow(10; $power+1) + 3) as $min
| ("3" + ((pow(10; $power) -1)|tostring) + "4"|tonumber) as $max
| range($min; $max; 10)
| select(is_prime) ) ;
task(2),
"\nStretch goal: \(count( task(4) ))"
- Output:
3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 Stretch goal: 2251
Julia
using Primes
isxbyx(n, base=10, dig=3) = n ÷ prevpow(base, n) == dig && n % base == dig
p3x3(N, base=10, dig=3) = [p for p in primes(N) if isxbyx(p, base, dig)]
for d in 1:2:9
println("\n$(d)x$d primes < 10000:")
foreach(p -> print(rpad(last(p), 5), first(p) % 11 == 0 ? "\n" : ""),
enumerate(p3x3(10000, 10, d)))
println("\nTotal $(d)x$d primes less than 1,000,000: ", length(p3x3(1_000_000, 10, d)), ".")
end
- Output:
1x1 primes < 10000: 11 101 131 151 181 191 1021 1031 1051 1061 1091 1151 1171 1181 1201 1231 1291 1301 1321 1361 1381 1451 1471 1481 1511 1531 1571 1601 1621 1721 1741 1801 1811 1831 1861 1871 1901 1931 1951 Total 1x1 primes less than 1,000,000: 2387. 3x3 primes < 10000: 3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 Total 3x3 primes less than 1,000,000: 2251. 5x5 primes < 10000: 5 Total 5x5 primes less than 1,000,000: 1. 7x7 primes < 10000: 7 727 757 787 797 7027 7057 7127 7177 7187 7207 7237 7247 7297 7307 7417 7457 7477 7487 7507 7517 7537 7547 7577 7607 7687 7717 7727 7757 7817 7867 7877 7907 7927 7937 Total 7x7 primes less than 1,000,000: 2104. 9x9 primes < 10000: 919 929 9029 9049 9059 9109 9199 9209 9239 9319 9349 9419 9439 9479 9539 9619 9629 9649 9679 9689 9719 9739 9749 9769 9829 9839 9859 9929 9949 Total 9x9 primes less than 1,000,000: 2053.
Mathematica / Wolfram Language
Cases[NestWhileList[NextPrime,
2, # < 4000 &], _?(IntegerDigits[#][[{1, -1}]] === {3, 3} &)]
- Output:
{3,313,353,373,383,3023,3083,3163,3203,3253,3313,3323,3343,3373,3413,3433,3463,3533,3583,3593,3613,3623,3643,3673,3733,3793,3803,3823,3833,3853,3863,3923,3943}
Nim
import strformat
func isPrime(n: Positive): bool =
for d in countup(3, n, 2):
if d * d > n: break
if n mod d == 0: return false
result = true
iterator primes3x3(lim: Natural): int =
assert lim >= 3
yield 3
var m = 100
while m * 3 < lim:
for n in countup(3 * m + 3, 4 * m - 7, 10):
if n > lim: break
if n.isPrime: yield n
m *= 10
var list: seq[int]
var count = 0
for n in primes3x3(1_000_000):
inc count
if n < 4000: list.add n
echo &"Found {list.len} primes starting and ending with 3 below 4_000:"
for i, n in list:
stdout.write &"{n:4}", if (i + 1) mod 11 == 0: '\n' else: ' '
echo &"\nFound {count} primes starting and ending with 3 below 1_000_000."
- Output:
Found 33 primes starting and ending with 3 below 4_000: 3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 Found 2251 primes starting and ending with 3 below 1_000_000.
Perl
#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Primes_whose_first_and_last_number_is_3
use warnings;
use ntheory qw( primes );
my @n33 = grep /^3/ && /3$/, @{ primes( 4000 ) };
my $n33 = grep /^3/ && /3$/, @{ primes( 1_000_000 ) };
print @n33 . " under 4000\n\n@n33" =~ s/.{75}\K /\n/gr,
"\n\n$n33 under 1000000\n";
- Output:
33 under 4000 3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 2251 under 1000000
Phix
Works for any digit, partly inspired by the Wren entry.
with javascript_semantics function primes_with_first_and_last_digit(integer d, p10) -- d should be 0..9 -- p10 should be 1 for 10, 4 for 10,000, 6 for 1,000,000, etc if d<0 or d>9 then crash("d is not a digit!") end if if d=2 or d=5 then return {d} end if if even(d) then return {} end if sequence res = filter({d},is_prime) for i=1 to p10-1 do integer p = power(10,i) for candidate = d*p+d to (d+1)*p-1 by 10 do if is_prime(candidate) then res &= candidate end if end for end for return res end function sequence res = primes_with_first_and_last_digit(3,4) string sres = join_by(apply(true,sprintf,{{"%5d"},res}),1,10) printf(1,"There are %d primes under 10,000 which begin and end in 3:\n%s\n",{length(res),sres}) res = primes_with_first_and_last_digit(3,6) printf(1,"There are %d primes under 1,000,000 which begin and end in 3\n",{length(res)})
- Output:
There are 33 primes under 10,000 which begin and end in 3: 3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 There are 2251 primes under 1,000,000 which begin and end in 3
Python
def prime(n):
if n == 1:
return False
if n == 2:
p.append(n)
return True
for y in p:
if n % y == 0:
return False
if y > int(n ** 0.5):
p.append(n)
return True
p = []
x = 1
stopper = 0
lis = []
for i in range(0, 1000000):
x += 1
if prime(x) == True:
str_x = str(x)
if str_x[0] == "3" and str_x[-1] == "3":
lis.append(x)
if int(x) == 4000 and stopper == 0:
print(f'There are {len(lis)} primes that start and end with 3 less than 4000')
for i in lis:
print(i)
print(f'There are {len(lis)} primes that start and end with 3 less than 1000000')
- Output:
There are 33 primes that start and end with 3 less than 4000 3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 There are 2251 primes that start and end with 3 less than 1000000
Raku
my $upto = 1e4;
for 1,3,5,7,9 -> $bracket {
print "\nPrimes up to $upto bracketed by $bracket - ";
say display ^$upto .grep: { .starts-with($bracket) && .ends-with($bracket) && .is-prime }
}
sub display ($list, :$cols = 10, :$fmt = '%6d', :$title = "{+$list} matching:\n" ) {
cache $list;
$title ~ $list.batch($cols)».fmt($fmt).join: "\n"
}
- Output:
Primes up to 10000 bracketed by 1 - 39 matching: 11 101 131 151 181 191 1021 1031 1051 1061 1091 1151 1171 1181 1201 1231 1291 1301 1321 1361 1381 1451 1471 1481 1511 1531 1571 1601 1621 1721 1741 1801 1811 1831 1861 1871 1901 1931 1951 Primes up to 10000 bracketed by 3 - 33 matching: 3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 Primes up to 10000 bracketed by 5 - 1 matching: 5 Primes up to 10000 bracketed by 7 - 35 matching: 7 727 757 787 797 7027 7057 7127 7177 7187 7207 7237 7247 7297 7307 7417 7457 7477 7487 7507 7517 7537 7547 7577 7607 7687 7717 7727 7757 7817 7867 7877 7907 7927 7937 Primes up to 10000 bracketed by 9 - 29 matching: 919 929 9029 9049 9059 9109 9199 9209 9239 9319 9349 9419 9439 9479 9539 9619 9629 9649 9679 9689 9719 9739 9749 9769 9829 9839 9859 9929 9949
REXX
This REXX version allows the specification of the limit to search for these types of primes (in base ten), and it also
allows the specification of what (both) the leading and trailing decimal digit must be.
Also, if a negative cols is specified, only the count of primes found is shown.
/*REXX pgm finds and displays primes (base ten) that contain a leading and trailing 3. */
parse arg hi cols dig . /*obtain optional argument from the CL.*/
if hi=='' | hi=="," then hi= 4000 /*Not specified? Then use the default.*/
if cols=='' | cols=="," then cols= 10 /* " " " " " " */
if dig=='' | dig=="," then dig= 3 /* " " " " " " */
call genP /*build array of semaphores for primes.*/
w= 10 /*width of a number in any column. */
title= ' primes N (in base ten) that have a leading and trailing digit of ' dig ,
" where N < " commas(hi)
if cols>0 then say ' index │'center(title, 1 + cols*(w+1) )
if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─')
found= 0; idx= 1 /*initialize # of primes found; IDX. */
$= /*list of primes that contain a string.*/
do j=1 for # /*find primes with leading/trailing dig*/
parse var @.j Ld 2 '' -1 Td /*obtain the leading and trailing digit*/
if Ld\==dig then iterate /*does prime contain a leading DIG ? */ /* ◄■■■■■■■ a filter.*/
if Td\==dig then iterate /* " " " " trailing ? ? */ /* ◄■■■■■■■ a filter.*/
found= found + 1 /*bump the number of primes found. */
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 a prime ──► $ list, allow big #*/
if found//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.*/
if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─')
say
say 'Found ' commas(found) title
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: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */
#=5; sq.#= @.# **2 /*number of primes so far; prime square*/
do j=@.#+2 by 2 to hi-1 /*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? */
do k=5 while sq.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; sq.#= j*j /*bump # of Ps; assign next P; P square*/
end /*j*/; return
- output when using the default inputs:
index │ primes N (in base ten) that have a leading and trailing digit of 3 where N < 4,000 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 3 313 353 373 383 3,023 3,083 3,163 3,203 3,253 11 │ 3,313 3,323 3,343 3,373 3,413 3,433 3,463 3,533 3,583 3,593 21 │ 3,613 3,623 3,643 3,673 3,733 3,793 3,803 3,823 3,833 3,853 31 │ 3,863 3,923 3,943 ───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 33 primes N (in base ten) that have a leading and trailing digit of 3 where N < 4,000
- output when using the default inputs of: 1000000 -1
Found 2,251 primes N (in base ten) that have a leading and trailing digit of 3 where N < 1,000,000
Ring
load "stdlib.ring"
see "working..." + nl
see "Primes whose first and last number is 3" + nl
row = 0
for n = 1 to 4000
strn = string(n)
if left(strn,1) = "3" and right(strn,1) = "3" and isprime(n)
see "" + n + " "
row++
if row%10 = 0
see nl
ok
ok
next
see nl + "Found " + row + " numbers" + nl
see "done..." + nl
- Output:
working... Primes whose first and last number is 3 3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 Found 33 numbers done...
RPL
Uses a candidate numbers generator to speed up execution.
≪ { } 3
WHILE DUP 4000 < REPEAT
IF DUP ISPRIME? THEN SWAP OVER + SWAP END
10 +
IF DUP MANT IP 3 ≠ THEN XPON 1 + ALOG 3 * 3 + END
END DROP
≫ '33PRIMES' STO
- Output:
1: { 3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 }
Ruby
require 'prime'
puts "Primes below #{n=4000} which start and end with #{d=3}: "
p Prime.each(n).select{|pr| p_d = pr.digits; p_d.first == d && p_d.last == d}
print "\nCount of primes below #{n=1_000_000} which start and en with #{d=3}: "
puts Prime.each(n).count{|pr| p_d = pr.digits; p_d.first == d && p_d.last == d}
- Output:
Primes below 4000 which start and end with 3: [3, 313, 353, 373, 383, 3023, 3083, 3163, 3203, 3253, 3313, 3323, 3343, 3373, 3413, 3433, 3463, 3533, 3583, 3593, 3613, 3623, 3643, 3673, 3733, 3793, 3803, 3823, 3833, 3853, 3863, 3923, 3943] Count of primes below 1000000 which start and en with 3: 2251
Sidef
func numbers_with_edges(upto, base = 10, s = [3]) {
Enumerator({|callback|
callback(s.digits2num(base))
for k in (0 .. base**(upto.len(base) - 2*s.len)) {
break if (s + k.digits(base) + s -> digits2num(base) > upto)
Inf.times { |j|
var d = (s + k.digits(base) + j.of(0) + s)
var n = d.digits2num(base)
(n <= upto) ? callback(n) : break
}
}
})
}
with (4e3) { |n|
var list = numbers_with_edges(n).grep{.is_prime}.sort
say "There are #{list.len} primes <= #{n.commify} which begin and end in 3:"
list.each_slice(10, {|*a| say a.map { '%5s' % _ }.join(' ') })
}
with (1e6) {|n|
var count = numbers_with_edges(n).grep{.is_prime}.len
say "\nThere are #{count} primes <= #{n.commify} which begin and end in 3"
}
- Output:
There are 33 primes <= 4,000 which begin and end in 3: 3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 There are 2251 primes <= 1,000,000 which begin and end in 3
Wren
Basic task
import "./math" for Int
import "./iterate" for Stepped
import "./fmt" for Fmt
var primes = []
for (seq in [ 3..3, 33..33, Stepped.new(303..393, 10), Stepped.new(3003..3993, 10) ]) {
for (e in seq) if (Int.isPrime(e)) primes.add(e)
}
System.print("Primes under 4,000 which begin and end in 3:")
Fmt.tprint("$,5d", primes, 11)
System.print("\nFound %(primes.count) such primes.")
- Output:
Primes under 4,000 which begin and end in 3: 3 313 353 373 383 3,023 3,083 3,163 3,203 3,253 3,313 3,323 3,343 3,373 3,413 3,433 3,463 3,533 3,583 3,593 3,613 3,623 3,643 3,673 3,733 3,793 3,803 3,823 3,833 3,853 3,863 3,923 3,943 Found 33 such primes.
More general
This version deals with primes (in base 10) beginning and ending with any specified digit and with up to a given number of digits.
import "./math" for Int
import "./iterate" for Stepped
import "./fmt" for Fmt
var getQualifyingPrimes = Fn.new { |x, d|
if (d.type != Num || !d.isInteger || d < 1) Fiber.abort("Invalid number of digits.")
if (x == 2 || x == 5) return [x]
if (x % 2 == 0) return []
var primes = []
var candidates = [x]
for (i in 1...d) {
var pow = 10.pow(i)
var start = x * (pow + 1)
var end = start + pow - 10
candidates.addAll(Stepped.new(start..end, 10).toList)
}
return candidates.where { |cand| Int.isPrime(cand) }.toList
}
var d = 4 // up to 'd' digits
for (x in [1, 2, 3, 5, 7, 9]) { // begins and ends with 'x'
var primes = getQualifyingPrimes.call(x, d)
var len = d + ((d-1)/3).floor
Fmt.print("Primes under $,%(len)d which begin and end in $d:", 10.pow(d), x)
Fmt.tprint("$,%(len)d", primes, 10)
System.print("\nFound %(primes.count) such primes.\n")
}
d = 6
for (x in [1, 3, 7, 9]) {
var primes = getQualifyingPrimes.call(x, d)
Fmt.print("Found $,d primes under $,d which begin and end with $d.\n", primes.count, 10.pow(d), x)
}
- Output:
Primes under 10,000 which begin and end in 1: 11 101 131 151 181 191 1,021 1,031 1,051 1,061 1,091 1,151 1,171 1,181 1,201 1,231 1,291 1,301 1,321 1,361 1,381 1,451 1,471 1,481 1,511 1,531 1,571 1,601 1,621 1,721 1,741 1,801 1,811 1,831 1,861 1,871 1,901 1,931 1,951 Found 39 such primes. Primes under 10,000 which begin and end in 2: 2 Found 1 such primes. Primes under 10,000 which begin and end in 3: 3 313 353 373 383 3,023 3,083 3,163 3,203 3,253 3,313 3,323 3,343 3,373 3,413 3,433 3,463 3,533 3,583 3,593 3,613 3,623 3,643 3,673 3,733 3,793 3,803 3,823 3,833 3,853 3,863 3,923 3,943 Found 33 such primes. Primes under 10,000 which begin and end in 5: 5 Found 1 such primes. Primes under 10,000 which begin and end in 7: 7 727 757 787 797 7,027 7,057 7,127 7,177 7,187 7,207 7,237 7,247 7,297 7,307 7,417 7,457 7,477 7,487 7,507 7,517 7,537 7,547 7,577 7,607 7,687 7,717 7,727 7,757 7,817 7,867 7,877 7,907 7,927 7,937 Found 35 such primes. Primes under 10,000 which begin and end in 9: 919 929 9,029 9,049 9,059 9,109 9,199 9,209 9,239 9,319 9,349 9,419 9,439 9,479 9,539 9,619 9,629 9,649 9,679 9,689 9,719 9,739 9,749 9,769 9,829 9,839 9,859 9,929 9,949 Found 29 such primes. Found 2,387 primes under 1,000,000 which begin and end with 1. Found 2,251 primes under 1,000,000 which begin and end with 3. Found 2,104 primes under 1,000,000 which begin and end with 7. Found 2,053 primes under 1,000,000 which begin and end with 9.
XPL0
func IsPrime(N); \Return 'true' if N is a prime number
int N, I;
[if N <= 1 then return false;
for I:= 2 to sqrt(N) do
if rem(N/I) = 0 then return false;
return true;
];
func Starts3(N); \Return 'true' if most significant digit is 3
int N;
[repeat N:= N/10;
until N = 0;
return rem(0) = 3;
];
int Count, N;
[Count:= 0;
N:= 3;
repeat if Starts3(N) then
if IsPrime(N) then
[Count:= Count+1;
if N < 4000 then
[IntOut(0, N);
if rem(Count/10) = 0 then CrLf(0) else ChOut(0, 9\tab\);
];
];
N:= N+10;
if N = 4003 then
[CrLf(0);
IntOut(0, Count);
Text(0, " such primes found below 4000.");
];
until N >= 1_000_000;
CrLf(0);
IntOut(0, Count);
Text(0, " such primes found below 1,000,000.
");
]
- Output:
3 313 353 373 383 3023 3083 3163 3203 3253 3313 3323 3343 3373 3413 3433 3463 3533 3583 3593 3613 3623 3643 3673 3733 3793 3803 3823 3833 3853 3863 3923 3943 33 such primes found below 4000. 2251 such primes found below 1,000,000.