Brilliant numbers: Difference between revisions
Added Easylang
(Created Nim solution.) |
(Added Easylang) |
||
| (10 intermediate revisions by 6 users not shown) | |||
Line 428:
Elapsed time: 1.50048 seconds
</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
function Compare(P1,P2: pointer): integer;
{Compare for quick sort}
begin
Result:=Integer(P1)-Integer(P2);
end;
procedure GetBrilliantNumbers(List: TList; Limit: integer);
{Return specified number of Brilliant Numbers in list}
var I,J,P,Stop: integer;
var Sieve: TPrimeSieve;
begin
Sieve:=TPrimeSieve.Create;
try
{build twices as many primes}
Sieve.Intialize(Limit*2);
{Pair every n-digt prime with every n-digit prime}
I:=2;
while true do
begin
J:=I;
{Put primes in J up to next power of 10 - 1}
Stop:=Trunc(Power(10,Trunc(Log10(I))+1));
while J<Stop do
begin
{Get the product}
P:=I * J;
{and store in the list}
List.Add(Pointer(P));
{Exit if we have all the numbers}
if List.Count>=Limit then break;
{Get next prime}
J:=Sieve.NextPrime(J);
end;
{break out of outer loop if done}
if List.Count>=Limit then break;
{Get next prime}
I:=Sieve.NextPrime(I);
end;
{The list won't be in order, so sort them}
List.Sort(Compare);
finally Sieve.Free; end;
end;
procedure ShowBrilliantNumbers(Memo: TMemo);
var List: TList;
var S: string;
var I,D,P: integer;
begin
List:=TList.Create;
try
{Get 10 million brilliant numbers}
GetBrilliantNumbers(List,1000000);
{Show the first 100}
S:='';
for I:=0 to 100-1 do
begin
S:=S+Format('%7d',[Integer(List[I])]);
if (I mod 10)=9 then S:=S+CRLF;
end;
Memo.Lines.Add(S);
{Show additional information}
for D:=1 to 8 do
begin
P:=Trunc(Power(10,D));
{Scan to find for 1st brilliant number >= 10^D }
for I:=0 to List.Count-1 do
if Integer(List[I])>=P then break;
{Display the info}
S:=Format('First brilliant number >= 10^%d is %10d',[D,Integer(List[I])]);
S:=S+Format(' at position %10D', [I]);
Memo.Lines.Add(S);
end;
finally List.Free; end;
end;
</syntaxhighlight>
{{out}}
<pre>
4 6 9 10 14 15 21 25 35 49
121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451
473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713
731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949
961 979 989 1003 1007 1027 1037 1067 1073 1079
1081 1121 1139 1147 1157 1159 1189 1207 1219 1241
1247 1261 1271 1273 1333 1343 1349 1357 1363 1369
First brilliant number >= 10^1 is 10 at position 3
First brilliant number >= 10^2 is 121 at position 10
First brilliant number >= 10^3 is 1003 at position 73
First brilliant number >= 10^4 is 10201 at position 241
First brilliant number >= 10^5 is 100013 at position 2504
First brilliant number >= 10^6 is 1018081 at position 10537
First brilliant number >= 10^7 is 10000043 at position 124363
First brilliant number >= 10^8 is 100140049 at position 573928
Elapsed Time: 185.451 ms.
</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
fastfunc factor num .
if num mod 2 = 0
if num = 2
return 1
.
return 2
.
i = 3
while i <= sqrt num
if num mod i = 0
return i
.
i += 2
.
return 1
.
func brilliant n .
f1 = factor n
if f1 = 1
return 0
.
f2 = n div f1
if floor log10 f1 <> floor log10 f2
return 0
.
if factor f1 = 1 and factor f2 = 1
return 1
.
return 0
.
proc main . .
i = 2
while cnt < 100
if brilliant i = 1
cnt += 1
write i & " "
.
i += 1
.
print "\n"
i = 2
cnt = 0
mag = 1
repeat
if brilliant i = 1
cnt += 1
if i >= mag
print i & " (" & cnt & ")"
mag *= 10
.
.
until mag = 10000000
i += 1
.
.
main
</syntaxhighlight>
{{out}}
<pre>
4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369
4 (1)
10 (4)
121 (11)
1003 (74)
10201 (242)
100013 (2505)
1018081 (10538)
</pre>
=={{header|Factor}}==
{{works with|Factor|0.99 2022-04-03}}
Line 471 ⟶ 654:
First brilliant number >= 1000000: 1018081 at position 10538
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">
function is_prime( n as uinteger ) as boolean
if n = 2 then return true
if n<2 or n mod 2 = 0 then return false
for i as uinteger = 3 to sqr(n) step 2
if (n mod i) = 0 then return false
next i
return true
end function
function first_prime_factor( n as uinteger ) as uinteger
if n mod 2 = 0 then return 2
for i as uinteger = 3 to sqr(n) step 2
if (n mod i) = 0 then return i
next i
return n
end function
dim as uinteger count = 0, n = 0, ff, sf, expo = 0
while count<100
ff = first_prime_factor(n)
sf = n/ff
if is_prime(sf) and len(str(ff)) = len(str(sf)) then
print n,
count = count + 1
if count mod 6 = 0 then print
end if
n = n + 1
wend
print
count = 0
n = 0
do
ff = first_prime_factor(n)
sf = n/ff
if is_prime(sf) and len(str(ff)) = len(str(sf)) then
count = count + 1
if n > 10^expo then
print n;" is brilliant #"; count
expo = expo + 1
if expo = 9 then end
end if
end if
n = n + 1
loop
</syntaxhighlight>
<pre>
4 6 9 10 14 15
21 25 35 49 121 143
169 187 209 221 247 253
289 299 319 323 341 361
377 391 403 407 437 451
473 481 493 517 527 529
533 551 559 583 589 611
629 649 667 671 689 697
703 713 731 737 767 779
781 793 799 803 817 841
851 869 871 893 899 901
913 923 943 949 961 979
989 1003 1007 1027 1037 1067
1073 1079 1081 1121 1139 1147
1157 1159 1189 1207 1219 1241
1247 1261 1271 1273 1333 1343
1349 1357 1363 1369
4 is brilliant #1
14 is brilliant #5
121 is brilliant #11
1003 is brilliant #74
10201 is brilliant #242
100013 is brilliant #2505
1018081 is brilliant #10538
10000043 is brilliant #124364
</pre>
=={{header|Go}}==
{{trans|Wren}}
Line 582 ⟶ 844:
First >= 10,000,000,000,000 is 34,896,253,010 in the series: 10,000,000,000,073
</pre>
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">import Control.Monad (join)
Line 1,370 ⟶ 1,633:
showList(List, Limit):-
findnsols(Limit, X, (member(X, List), writef('%5r', [X])), _),
nl, fail.
showList(
do:-findnsols(100, B, isBrilliant(B), BList),!,
showList(BList, 10),nl,
findall(N, (between(1, 6, X), N is 10^X), LimitList),
run(LimitList).
</syntaxhighlight>
Line 1,599 ⟶ 1,855:
First >= 100,000,000 is 573929ᵗʰ in the series: 100,140,049
First >= 1,000,000,000 is 7407841ˢᵗ in the series: 1,000,000,081</pre>
=={{header|RPL}}==
A fast semiprime checker was needed here.
{| class="wikitable" ≪
! RPL code
! Comment
|-
|
≪ DUP √ CEIL 0 → max div
≪ 0
2 max '''FOR''' j
'''WHILE''' OVER j MOD NOT '''REPEAT'''
SWAP j / SWAP 1 + j 'div' STO '''END'''
'''IF''' DUP 2 > '''THEN''' max 'j' STO '''END'''
'''NEXT'''
'''IF''' OVER 1 > '''THEN''' 1 + '''END'''
SWAP DROP 2 == div *
≫ ≫ ‘<span style="color:blue">SPR1?</span>’ STO
≪
'''IF''' DUP <span style="color:blue">SPR1?</span> DUP '''THEN'''
DUP2 / XPON SWAP XPON == SWAP DROP
'''ELSE''' DROP2 0 '''END'''
≫ ‘<span style="color:blue">BRIL?</span>’ STO
|
<span style="color:blue">SPR1?</span> ''( n → divisor ) ''
cnt = 0;
for j = 2 to ceiling(sqrt(n))
while (n % j == 0)
n /= j ; ++cnt ; div = j ;
if cnt > 2 then break;
if (num > 1) ++cnt;
return divisor if semiprime, otherwise zero
<span style="color:blue">BRIL?</span> ''( n → boolean ) ''
if semiprime then
compare divisors' size
else not a brilliant number
|}
≪ { } 1 '''WHILE''' OVER SIZE 100 < '''REPEAT''' '''IF''' DUP <span style="color:blue">BRIL?</span> '''THEN''' SWAP OVER + SWAP '''END''' 1 + '''END''' DROP ≫ EVAL
≪ { } 1 5 '''FOR''' n n ALOG '''WHILE''' DUP <span style="color:blue">BRIL?</span> NOT '''REPEAT''' 1 + '''END''' + '''NEXT''' ≫ EVAL
{{out}}
<pre>
2: { 4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299 319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583 589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841 851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079 1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369 }
1: { 10 121 1003 10201 100013 1018081 }
</pre>
=={{header|Rust}}==
{{trans|C++}}
Line 1,716 ⟶ 2,021:
Elapsed time: 1515 milliseconds
</pre>
=={{header|Scala}}==
<syntaxhighlight lang="scala">
val primes = 2 #:: LazyList.from(3, 2) // simple prime
.filter(p => (3 to math.sqrt(p).ceil.toInt by 2).forall(p % _ > 0))
def brilliantSemiPrimes(limit: Int): Seq[Int] = {
def iter(primeList: LazyList[Int], bLimit: Int, acc: Seq[Int]): Seq[Int] = {
val (start, tail) = (primeList.head, primeList.tail)
val brilliants = primeList
.takeWhile(_ <= bLimit)
.map(_ * start)
.takeWhile(_ <= limit)
if (brilliants.isEmpty) return acc
val bLimit1 = if (tail.head > bLimit) 10 * bLimit else bLimit
iter(tail, bLimit1, brilliants.toSeq ++ acc)
}
iter(primes, 10, Seq()).sorted
}
@main def main = {
val start = System.currentTimeMillis
val brList = brilliantSemiPrimes(1500).take(100)
val duration = System.currentTimeMillis - start
for (group <- brList.grouped(20))
println(group.map("%4d".format(_)).mkString(" "))
println(s"time elapsed: $duration ms\n")
for (limit <- (1 to 6).map(math.pow(10,_).toInt)) {
val start = System.currentTimeMillis
val (bril, index) = brilliantSemiPrimes((limit * 1.25).toInt)
.zipWithIndex
.dropWhile((b, _i) => b < limit)
.head
val duration = System.currentTimeMillis - start
println(f"first >= $limit%7d is $bril%7d at position ${index+1}%5d [time(ms) $duration%2d]")
}
}
</syntaxhighlight>
{{out}}
<pre>
4 6 9 10 14 15 21 25 35 49 121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451 473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713 731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949 961 979 989 1003 1007 1027 1037 1067 1073 1079
1081 1121 1139 1147 1157 1159 1189 1207 1219 1241 1247 1261 1271 1273 1333 1343 1349 1357 1363 1369
time elapsed: 3 ms
first >= 10 is 10 at position 4 [time(ms) 1]
first >= 100 is 121 at position 11 [time(ms) 0]
first >= 1000 is 1003 at position 74 [time(ms) 1]
first >= 10000 is 10201 at position 242 [time(ms) 2]
first >= 100000 is 100013 at position 2505 [time(ms) 6]
first >= 1000000 is 1018081 at position 10538 [time(ms) 11]
</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func is_briliant_number(n) {
Line 1,904 ⟶ 2,264:
=={{header|Wren}}==
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
Line 1,943 ⟶ 2,301:
brilliant.sort()
brilliant = brilliant[0..99]
Fmt.tprint("$4d", brilliant, 10)
System.print()
for (k in 1..12) {
Line 1,980 ⟶ 2,338:
First >= 1,000,000,000,000 is 2,409,600,866th in the series: 1,000,006,000,009
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">
| |||