Prime numbers which contain 123: Difference between revisions
Content deleted Content added
Thundergnat (talk | contribs) m syntax highlighting fixup automation |
|||
| (10 intermediate revisions by 9 users not shown) | |||
Line 204:
{{out}}
<pre>Same as FreeBASIC entry.</pre>
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
bool isPrime( int number ) {
if ( number < 2 ) {
return false ;
}
int stop = std::sqrt( static_cast<double>( number ) ) ;
for ( int i = 2 ; i <= stop ; ++i )
if ( number % i == 0 )
return false ;
return true ;
}
bool condition( int n ) {
std::string numberstring { std::to_string( n ) } ;
return isPrime( n ) && numberstring.find( "123" ) != std::string::npos ;
}
int main( ) {
std::vector<int> wantedPrimes ;
for ( int i = 1 ; i < 100000 ; i++ ) {
if ( condition( i ) )
wantedPrimes.push_back( i ) ;
}
int count = 0 ;
for ( int i : wantedPrimes ) {
std::cout << i << ' ' ;
count++ ;
if ( count % 10 == 0 ) {
std::cout << std::endl ;
}
}
count = wantedPrimes.size( ) ;
for ( int i = wantedPrimes.back( ) + 1 ; i < 1000000 ; i++ ) {
if ( condition ( i ) )
count++ ;
}
std::cout << std::endl ;
std::cout << "There are " << count << " such numbers below 1000000!\n" ;
return 0 ;
}</syntaxhighlight>
{{out}}
<pre>
1123 1231 1237 8123 11239 12301 12323 12329 12343 12347
12373 12377 12379 12391 17123 20123 22123 28123 29123 31123
31231 31237 34123 37123 40123 41231 41233 44123 47123 49123
50123 51239 56123 59123 61231 64123 65123 70123 71233 71237
76123 81233 81239 89123 91237 98123
There are 451 such numbers below 1000000!
</pre>
=={{header|Clojure}}==
<syntaxhighlight lang="clojure">
(ns primes-found-app
(:require [clojure.string :as str])
(:gen-class))
(defn is-prime? [n]
(if (< 1 n)
(empty? (filter #(= 0 (mod n %)) (range 2 n)))
false))
(defn get-prime-numbers [n]
(filter is-prime? (take n (range))))
(defn numbers-to-str [xs]
(map #(str %) xs))
(defn is-includes-123? [s]
(str/includes? s "123"))
(defn solution [number]
(->>
(get-prime-numbers number)
(numbers-to-str)
(filter is-includes-123?)))
(defn main []
(let [result (count (solution 1000000))]
(prn (solution 100000))
(format "There are %d primes that contain '123' below 1000000." result)
))
(main)
</syntaxhighlight>
{{out}}
<pre>
("1123" "1231" "1237" "8123" "11239" "12301" "12323" "12329" "12343" "12347" "12373" "12377" "12379" "12391" "17123" "20123" "22123" "28123" "29123" "31123" "31231" "31237" "34123" "37123" "40123" "41231" "41233" "44123" "47123" "49123" "50123" "51239" "56123" "59123" "61231" "64123" "65123" "70123" "71233" "71237" "76123" "81233" "81239" "89123" "91237" "98123")
"There are 451 primes that contain '123' below 1000000."
</pre>
=={{header|CLU}}==
Line 254 ⟶ 351:
76123 81233 81239 89123 91237 98123
There are 451 primes that contain '123' below 1,000,000.</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
procedure ShowPrimesWith123(Memo: TMemo);
var N,Sum,Cnt1,Cnt2: integer;
var NS,S: string;
begin
Cnt1:=0;
Cnt2:=0;
Sum:=0;
for N:=123 to 1000000-1 do
if IsPrime(N) then
begin
NS:=IntToStr(N);
if Pos('123',NS)>0 then
begin
Inc(Cnt1);
if N<100000 then
begin
Inc(Cnt2);
S:=S+Format('%6d',[N]);
If (Cnt2 mod 8)=0 then S:=S+CRLF;
end;
end;
end;
Memo.Lines.Add(S);
Memo.Lines.Add('Count < 100,000 = '+IntToStr(Cnt2));
Memo.Lines.Add('Count < 1,000,000 = '+IntToStr(Cnt1));
end;
</syntaxhighlight>
{{out}}
<pre>
1123 1231 1237 8123 11239 12301 12323 12329
12343 12347 12373 12377 12379 12391 17123 20123
22123 28123 29123 31123 31231 31237 34123 37123
40123 41231 41233 44123 47123 49123 50123 51239
56123 59123 61231 64123 65123 70123 71233 71237
76123 81233 81239 89123 91237 98123
Count < 100,000 = 46
Count < 1,000,000 = 451
Elapsed Time: 147.996 ms.
</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
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 dig123 n .
while n > 0
if n mod 1000 = 123
return 1
.
n = n div 10
.
return 0
.
prim = 2
repeat
if dig123 prim = 1
write prim & " "
.
prim = nextprim prim
until prim >= 100000
.
</syntaxhighlight>
{{out}}
<pre>
1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123
</pre>
=={{header|F_Sharp|F#}}==
Line 376 ⟶ 566:
Encontrados 451 números primos por debajo de 1000000
</pre>
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
include "NSLog.incl"
local fn IsPrime( n as long ) as BOOL
long i
BOOL result = YES
if ( n < 2 ) then result = NO : exit fn
for i = 2 to n + 1
if ( i * i <= n ) and ( n mod i == 0 )
result = NO : exit fn
end if
next
end fn = result
local fn PrimeWith123( limit as long )
long i, column = 1
CFStringRef numStr
NSLog( @"Prime numbers less than 100,000 which contain '123':\n" )
for i = 1 to limit
numStr = fn StringWithFormat( @"%lu", i )
if ( fn IsPrime( i ) ) and ( fn StringContainsString( numStr, @"123" ) )
NSLog( @"%-6lu\b", i )
if column == 10 then column = 0 : NSLog( @"" )
column++
end if
next
end fn
fn PrimeWith123( 100000 )
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
Prime numbers less than 100,000 which contain '123':
12373 12377 12379 12391 17123 20123 22123 28123 29123 31123
31231 31237 34123 37123 40123 41231 41233 44123 47123 49123
50123 51239 56123 59123 61231 64123 65123 70123 71233 71237
76123 81233 81239 89123 91237 98123
</pre>
Line 440 ⟶ 678:
Found 451 such primes under 1,000,000.
</pre>
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">
import Data.List ( isInfixOf )
isPrime :: Int -> Bool
isPrime n
|n < 2 = 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 && isInfixOf "123" ( show n )
solution :: [Int]
solution = filter condition [2..99999]</syntaxhighlight>
{{out}}
<pre>
[1123,1231,1237,8123,11239,12301,12323,12329,12343,12347,12373,12377,12379,12391,17123,20123,22123,28123,29123,31123,31231,31237,34123,37123,40123,41231,41233,44123,47123,49123,50123,51239,56123,59123,61231,64123,65123,70123,71233,71237,76123,81233,81239,89123,91237,98123]
</pre>
Line 742 ⟶ 1,002:
Igual que la entrada de FreeBASIC.
</pre>
=={{header|Quackery}}==
<code>eratosthenes</code> and <code>isprime</code> are defined at [[Sieve of Eratosthenes#Quackery]].
<syntaxhighlight lang="Quackery"> 100000 eratosthenes
[ false swap
[ dup 122 > while
dup 1000 mod
123 = iff
[ dip not ]
done
10 / again ]
drop ] is contains123 ( n --> b )
[]
100000 times
[ i^ isprime if
[ i^ contains123 if
[ i^ join ] ] ]
[] swap witheach
[ number$ nested join ]
48 wrap$</syntaxhighlight>
{{out}}
<pre>1123 1231 1237 8123 11239 12301 12323 12329
12343 12347 12373 12377 12379 12391 17123 20123
22123 28123 29123 31123 31231 31237 34123 37123
40123 41231 41233 44123 47123 49123 50123 51239
56123 59123 61231 64123 65123 70123 71233 71237
76123 81233 81239 89123 91237 98123</pre>
=={{header|Raku}}==
<syntaxhighlight lang="raku" line>my @p123 = ^∞ .grep: { (.
put display @p123[^(@p123.first: * > 1e5, :k)];
Line 871 ⟶ 1,165:
done...
</pre>
=={{header|RPL}}==
===Brute force===
≪ ALOG → max
≪ { } 1123
'''WHILE''' DUP max < '''REPEAT'''
NEXTPRIME
'''IF''' DUP →STR "123" POS '''THEN''' SWAP OVER + SWAP '''END'''
'''END''' NIP
≫ ≫ '<span style="color:blue">TASK</span>’ STO
{{out}}
<pre>
1: { 1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 }
</pre>
Runs in 12 minutes 45 seconds on a HP-50g
===Lexicographic approach===
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
3 - DUP ALOG 1 - { } → ndigits maxleft results
≪ 0
'''DO'''
DUP DUP "" IFTE
ndigits OVER SIZE - ALOG 1 +
DUP 2 x 3 - '''FOR''' j
DUP "123" + j →STR TAIL + STR→
'''IF''' DUP ISPRIME? '''THEN''' 'results' STO+ '''ELSE''' DROP '''END'''
2 '''STEP'''
DROP 1 +
'''UNTIL''' DUP maxleft > '''END'''
DROP results
≫ ≫ '<span style="color:blue">PR123N</span>’ STO
|
<span style="color:blue">PR123N</span> ''( n_digits → { primes_with_123 } ) ''
n_digits -= 3 ; maxleft = 10^n_digits - 1
leftval = 0
loop
left = leftval == 0 ? "" ; leftval
tmp = 10^(n_digits - length(leftval)) + 1
for j = tmp to (tmp*2 - 3) step 2
n = left + "123" + j[2..]
add n to results if prime
next j
leftval++
end loop
display results (unsorted)
|}
4 <span style="color:blue">PR123N</span> 5 <span style="color:blue">PR123N</span> + SORT
Runs in 22 seconds on a HP-50g (35 times faster than brute force) - same results as above.
Finding the 451 primes under one million takes 4 minutes 30 seconds.
=={{header|Ruby}}==
Line 884 ⟶ 1,234:
451 123-primes below 1 million.
</pre>
=={{header|Sidef}}==
Line 937 ⟶ 1,286:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
The only number under 1,000 which can possibly satisfy the task description is 123 and that's clearly divisible by 3 and hence composite.
<syntaxhighlight lang="
import "./fmt" for Fmt
var limit = 1e5
Line 947 ⟶ 1,294:
var results = primes.where { |p| p < limit && p.toString.contains("123") }.toList
Fmt.print("Primes under $,d which contain '123' when expressed in decimal:", limit)
Fmt.tprint("$,7d", results, 10)
Fmt.print("\nFound $,d such primes under $,d.", results.count, limit)
| |||