Frobenius numbers: Difference between revisions
Added Easylang
SqrtNegInf (talk | contribs) (→{{header|Perl}}: added alternative method) |
(Added Easylang) |
||
| (42 intermediate revisions by 23 users not shown) | |||
Line 3:
;Task:
Find and display here on this page the Frobenius numbers that are <big> < </big> 10,000.
The series is defined by:
<big> FrobeniusNumber(n) = prime(n) * prime(n+1) - prime(n) - prime(n+1)</big>
:::: prime(1) = 2
:::: prime(2) = 3
:::: prime(3) = 5
:::: prime(4) = 7
::::: •
::::: •
::::: •
</big>
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F isPrime(v)
I v <= 1
R 0B
I v < 4
R 1B
I v % 2 == 0
R 0B
I v < 9
R 1B
I v % 3 == 0
R 0B
E
V r = round(pow(v, 0.5))
V f = 5
L f <= r
I v % f == 0 | v % (f + 2) == 0
R 0B
f += 6
R 1B
V pn = 2
V n = 0
L(i) (3..).step(2)
I isPrime(i)
n++
V f = (pn * i) - pn - i
I f > 10000
L.break
print(n‘ => ’f)
pn = i</syntaxhighlight>
{{out}}
<pre>
1 => 1
2 => 7
3 => 23
4 => 59
5 => 119
6 => 191
7 => 287
8 => 395
9 => 615
10 => 839
11 => 1079
12 => 1439
13 => 1679
14 => 1931
15 => 2391
16 => 3015
17 => 3479
18 => 3959
19 => 4619
20 => 5039
21 => 5615
22 => 6395
23 => 7215
24 => 8447
25 => 9599
</pre>
=={{header|Action!}}==
{{libheader|Action! Sieve of Eratosthenes}}
<syntaxhighlight lang="action!">INCLUDE "H6:SIEVE.ACT"
INT FUNC NextPrime(INT p BYTE ARRAY primes)
DO
p==+1
UNTIL primes(p)
OD
RETURN (p)
PROC Main()
DEFINE MAXNUM="200"
BYTE ARRAY primes(MAXNUM+1)
INT p1,p2,f
Put(125) PutE() ;clear the screen
Sieve(primes,MAXNUM+1)
p2=2
DO
p1=p2
p2=NextPrime(p2,primes)
f=p1*p2-p1-p2
IF f<10000 THEN
PrintI(f) Put(32)
ELSE
EXIT
FI
OD
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Frobenius_numbers.png Screenshot from Atari 8-bit computer]
<pre>
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
</pre>
=={{header|ALGOL 68}}==
<
# Frobenius(n) = ( prime(n) * prime(n+1) ) - prime(n) - prime(n+1) #
# reurns a list of primes up to n #
Line 46 ⟶ 150:
print( ( " ", whole( frobenius number, 0 ) ) )
OD
END</
{{out}}
<pre>
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
</pre>
=={{header|APL}}==
{{works with|Dyalog APL}}
<
{{out}}
<pre>1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599</pre>
=={{header|AppleScript}}==
<syntaxhighlight lang="applescript">on isPrime(n)
if (n < 4) then return (n > 1)
if ((n mod 2 is 0) or (n mod 3 is 0)) then return false
repeat with i from 5 to (n ^ 0.5) div 1 by 6
if ((n mod i is 0) or (n mod (i + 2) is 0)) then return false
end repeat
return true
end isPrime
on Frobenii(max)
script o
property frobs : {}
end script
set p to 2
set n to 3
repeat
if (isPrime(n)) then
set frob to p * n - p - n
if (frob > max) then exit repeat
set end of o's frobs to frob
set p to n
end if
set n to n + 2
end repeat
return o's frobs
end Frobenii
Frobenii(9999)</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">{1, 7, 23, 59, 119, 191, 287, 395, 615, 839, 1079, 1439, 1679, 1931, 2391, 3015, 3479, 3959, 4619, 5039, 5615, 6395, 7215, 8447, 9599}</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">primes: select 0..10000 => prime?
frobenius: function [n] -> sub sub primes\[n] * primes\[n+1] primes\[n] primes\[n+1]
frob: 0
lst: new []
j: new 0
while [frob < 10000] [
'lst ++ frob: <= frobenius j
inc 'j
]
loop split.every:10 chop lst 'a ->
print map a => [pad to :string & 5]</syntaxhighlight>
{{out}}
<pre> 1 7 23 59 119 191 287 395 615 839
1079 1439 1679 1931 2391 3015 3479 3959 4619 5039
5615 6395 7215 8447 9599</pre>
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">n := 0, i := 1, pn := 2
loop {
if isprime(i+=2) {
if ((f := pn*i - pn - i) > 10000)
break
result .= SubStr(" " f, -3) . (Mod(++n, 5) ? "`t" : "`n")
pn := i
}
}
MsgBox % result
return
isPrime(n, p=1) {
if (n < 2)
return false
if !Mod(n, 2)
return (n = 2)
if !Mod(n, 3)
return (n = 3)
while ((p+=4) <= Sqrt(n))
if !Mod(n, p)
return false
else if !Mod(n, p+=2)
return false
return true
}</syntaxhighlight>
{{out}}
<pre> 1 7 23 59 119
191 287 395 615 839
1079 1439 1679 1931 2391
3015 3479 3959 4619 5039
5615 6395 7215 8447 9599</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f FROBENIUS_NUMBERS.AWK
# converted from FreeBASIC
Line 87 ⟶ 283:
return(1)
}
</syntaxhighlight>
{{out}}
<pre>
Line 95 ⟶ 291:
Frobenius numbers 3-9999: 25
</pre>
=={{header|BASIC}}==
<syntaxhighlight lang="basic">10 DEFINT A-Z
20 LM = 10000
30 M = SQR(LM)+1
40 DIM P(M)
50 FOR I=2 TO SQR(M)
60 IF P(I)=0 THEN FOR J=I+I TO M STEP I: P(J)=1: NEXT J
70 NEXT I
80 FOR I=2 TO M
90 IF P(I)=0 THEN P(C)=I: C=C+1
100 NEXT I
110 FOR N=0 TO C-2
120 PRINT P(N)*P(N+1)-P(N)-P(N+1),
130 NEXT N</syntaxhighlight>
{{out}}
<pre> 1 7 23 59 119
191 287 395 615 839
1079 1439 1679 1931 2391
3015 3479 3959 4619 5039
5615 6395 7215 8447 9599</pre>
=={{header|BASIC256}}==
<syntaxhighlight lang="basic256">
n = 0
lim = 10000
k = sqr(lim) + 1
dim P(k)
for i = 2 to sqr(k)
if P[i] = 0 then
for j = i + i to k step i
P[j] = 1
next j
end if
next i
for i = 2 to k-1
if P[i] = 0 then P[n] = i: n += 1
next i
for i = 0 to n - 2
print i+1; " => "; P[i] * P[i + 1] - P[i] - P[i + 1]
next i
end
</syntaxhighlight>
=={{header|BCPL}}==
<
manifest $( limit = 10000 $)
Line 150 ⟶ 391:
writef("%N*N", frob(primes, n))
freevec(primes)
$)</
{{out}}
<pre>1
Line 179 ⟶ 420:
=={{header|C}}==
<
#include <stdlib.h>
#include <math.h>
Line 216 ⟶ 457:
return 0;
}</
{{out}}
<pre>1
Line 244 ⟶ 485:
9599</pre>
=={{header|C
Asterisks mark the non-primes among the numbers.
<
class Program {
Line 268 ⟶ 509:
if (!flags[j]) { yield return j;
for (int k = sq, i = j << 1; k <= lim; k += i) flags[k] = true; }
for (; j <= lim; j += 2) if (!flags[j]) yield return j; } }</
{{out}}
Line 293 ⟶ 534:
=={{header|C++}}==
{{libheader|Primesieve}}
<
#include <iomanip>
#include <iostream>
Line 332 ⟶ 573:
}
std::cout << '\n';
}</
{{out}}
Line 354 ⟶ 595:
770879 776159* 781451 802715 824459* 835379* 851903 868607 879839* 889239
900591 919631* 937019 946719 958431 972179 986039
</pre>
=={{header|Cowgol}}==
<syntaxhighlight lang="cowgol">include "cowgol.coh";
const LIMIT := 10000;
sub sqrt(n: intptr): (x0: intptr) is
var x1: intptr;
if n <= 1 then
x0 := 1;
else
x0 := n >> 1;
x1 := (x0 + n/x0) >> 1;
while x1 < x0 loop
x0 := x1;
x1 := (x0 + n/x0) >> 1;
end loop;
end if;
end sub;
sub sieve(max: intptr, buf: [uint16]): (count: uint16) is
var sbuf := buf as [uint8] + max;
MemZero(sbuf, max);
var i: intptr := 2;
while i*i <= max loop
if [sbuf+i] == 0 then
var j := i+i;
while j <= max loop
[sbuf+j] := 1;
j := j+i;
end loop;
end if;
i := i+1;
end loop;
count := 0;
i := 2;
while i <= max loop
if [sbuf+i] == 0 then
[buf] := i as uint16;
buf := @next buf;
count := count + 1;
end if;
i := i + 1;
end loop;
end sub;
var primes: uint16[LIMIT + 1];
var nprimes := sieve(sqrt(LIMIT)+1, &primes[0]);
var n: uint16 := 0;
while n < nprimes-1 loop
print_i16(primes[n] * primes[n+1] - primes[n] - primes[n+1]);
print_nl();
n := n + 1;
end loop;</syntaxhighlight>
{{out}}
<pre>1
7
23
59
119
191
287
395
615
839
1079
1439
1679
1931
2391
3015
3479
3959
4619
5039
5615
6395
7215
8447
9599</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
function IsPrime(N: integer): boolean;
{Optimised prime test - about 40% faster than the naive approach}
var I,Stop: integer;
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));
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;
function GetNextPrime(Start: integer): integer;
{Get the next prime number after Start}
begin
repeat Inc(Start)
until IsPrime(Start);
Result:=Start;
end;
procedure ShowFrobeniusNumbers(Memo: TMemo);
var N,N1,FN,Cnt: integer;
begin
N:=2;
Cnt:=0;
while true do
begin
Inc(Cnt);
N1:=GetNextPrime(N);
FN:=N * N1 - N - N1;
N:=N1;
if FN>10000 then break;
Memo.Lines.Add(Format('%2d = %5d',[Cnt,FN]));
end;
end;
</syntaxhighlight>
{{out}}
<pre>
1 = 1
2 = 7
3 = 23
4 = 59
5 = 119
6 = 191
7 = 287
8 = 395
9 = 615
10 = 839
11 = 1079
12 = 1439
13 = 1679
14 = 1931
15 = 2391
16 = 3015
17 = 3479
18 = 3959
19 = 4619
20 = 5039
21 = 5615
22 = 6395
23 = 7215
24 = 8447
25 = 9599
</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
.
prim = 2
repeat
prim0 = prim
prim = nextprim prim
x = prim0 * prim - prim0 - prim
until x >= 10000
write x & " "
.
</syntaxhighlight>
{{out}}
<pre>
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
</pre>
=={{header|Factor}}==
{{works with|Factor|0.99 2021-02-05}}
<
"Frobenius numbers < 10,000:" print
Line 364 ⟶ 805:
[ nip dup next-prime ] [ * ] [ [ - ] dip - ] 2tri
dup 10,000 <
] [ . ] while 3drop</
{{out}}
<pre style="height:14em">
Line 396 ⟶ 837:
=={{header|Fermat}}==
<
for n = 1 to 25 do !!Frobenius(n) od</
{{out}}
<pre>
Line 428 ⟶ 869:
=={{header|FreeBASIC}}==
<
dim as integer pn=2, n=0, f
Line 439 ⟶ 880:
pn = i
end if
next i</
{{out}}
<pre>
Line 468 ⟶ 909:
25 9599
</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
void local fn ListFrobenius( upperLimit as long )
long i, pn = 2, n = 0, f, r = 0
NSLog( @"Frobenius numbers through %ld:", upperLimit )
for i = 3 to upperLimit - 1 step 2
if ( fn IsPrime(i) )
n++
f = pn * i - pn - i
if ( f > upperLimit ) then break
NSLog( @"%7ld\b", f )
r++
if r mod 5 == 0 then NSLog( @"" )
pn = i
end if
next
end fn
fn ListFrobenius( 100000 )
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
Frobenius numbers through 100000:
1 7 23 59 119
191 287 395 615 839
1079 1439 1679 1931 2391
3015 3479 3959 4619 5039
5615 6395 7215 8447 9599
10199 10811 11447 12095 14111
16379 17679 18767 20423 22199
23399 25271 26891 28551 30615
32039 34199 36479 37631 38807
41579 46619 50171 51527 52895
55215 57119 59999 63999 67071
70215 72359 74519 77279 78959
82343 89351 94859 96719 98591
</pre>
=={{header|Go}}==
{{trans|Wren}}
{{libheader|Go-rcu}}
<syntaxhighlight lang="go">package main
import (
"fmt"
"rcu"
)
func main() {
primes := rcu.Primes(101)
var frobenius []int
for i := 0; i < len(primes)-1; i++ {
frob := primes[i]*primes[i+1] - primes[i] - primes[i+1]
if frob >= 10000 {
break
}
frobenius = append(frobenius, frob)
}
fmt.Println("Frobenius numbers under 10,000:")
for i, n := range frobenius {
fmt.Printf("%5s ", rcu.Commatize(n))
if (i+1)%9 == 0 {
fmt.Println()
}
}
fmt.Printf("\n\n%d such numbers found.\n", len(frobenius))
}</syntaxhighlight>
{{out}}
<pre>
Frobenius numbers under 10,000:
1 7 23 59 119 191 287 395 615
839 1,079 1,439 1,679 1,931 2,391 3,015 3,479 3,959
4,619 5,039 5,615 6,395 7,215 8,447 9,599
25 such numbers found.
</pre>
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">primes = 2 : sieve [3,5..]
where sieve (x:xs) = x : sieve (filter (\y -> y `mod` x /= 0) xs)
frobenius = zipWith (\a b -> a*b - a - b) primes (tail primes)</syntaxhighlight>
<pre>λ> takeWhile (< 10000) frobenius
[1,7,23,59,119,191,287,395,615,839,1079,1439,1679,1931,2391,3015,3479,3959,4619,5039,5615,6395,7215,8447,9599]</pre>
=={{header|J}}==
<syntaxhighlight lang
echo frob i. 25</
(Note that <code>frob</code> counts prime numbers starting from 0 (which gives 2), so for some contexts the function to calculate frobenius numbers would be <code>frob@<:</code>.)
{{out}}
<pre>1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599</pre>
Line 477 ⟶ 1,027:
=={{header|Java}}==
Uses the PrimeGenerator class from [[Extensible prime generator#Java]].
<
public static void main(String[] args) {
final int limit = 1000000;
Line 512 ⟶ 1,062:
return true;
}
}</
{{out}}
Line 534 ⟶ 1,084:
770879 776159* 781451 802715 824459* 835379* 851903 868607 879839* 889239
900591 919631* 937019 946719 958431 972179 986039
</pre>
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
The solution offered here is based on a function that can in principle generate an unbounded stream of Frobenius numbers without relying on the precomputation or storage of an array of primes except as may be used by `is_prime`.
The following is also designed to take advantage of gojq's support for unbounded-precision integer arithmetic.
See e.g. [[Erd%C5%91s-primes#jq]] for a suitable implementation of `is_prime`.
<syntaxhighlight lang="jq"># Generate a stream of Frobenius numbers up to an including `.`;
# specify `null` or `infinite` to generate an unbounded stream.
def frobenius:
. as $limit
| label $out
| foreach (range(3;infinite;2) | select(is_prime)) as $p ({prev: 2};
(.prev * $p - .prev - $p) as $frob
| if ($limit != null and $frob > $limit then break $out
else .frob = $frob
end
| .prev = $p;
.frob);
9999 | frobenius</syntaxhighlight>
{{out}}
<pre>
1
7
23
59
119
191
287
395
615
839
1079
1439
1679
1931
2391
3015
3479
3959
4619
5039
5615
6395
7215
8447
9599
</pre>
=={{header|Julia}}==
<
const primeslt10k = primes(10000)
Line 561 ⟶ 1,163:
testfrobenius()
</
<pre>
Frobenius numbers less than 1,000,000 (an asterisk marks the prime ones).
Line 582 ⟶ 1,184:
900591 919631* 937019 946719 958431 972179 986039
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[fn]
fn[n_] := Prime[n] Prime[n + 1] - Prime[n] - Prime[n + 1]
a = -1;
i = 1;
res = {};
While[a < 10^4,
a = fn[i];
i++;
If[a < 10^4, AppendTo[res, a]]
]
res</syntaxhighlight>
{{out}}
<pre>{1,7,23,59,119,191,287,395,615,839,1079,1439,1679,1931,2391,3015,3479,3959,4619,5039,5615,6395,7215,8447,9599}</pre>
=={{header|Nim}}==
As I like iterators, I used one for (odd) primes and one for Frobenius numbers. Of course, there are other ways to proceed.
<syntaxhighlight lang="nim">import sequtils, strutils
func isOddPrime(n: Positive): bool =
if n mod 3 == 0: return n == 3
var d = 5
while d * d <= n:
if n mod d == 0: return false
inc d, 2
if n mod d == 0: return false
inc d, 4
result = true
iterator oddPrimes(): int =
yield 3
var n = 5
while true:
if n.isOddPrime: yield n
inc n, 2
if n.isOddPrime: yield n
inc n, 4
iterator frobenius(lim: Positive): int =
var p1 = 2
for p2 in oddPrimes():
let f = p1 * p2 - p1 - p2
if f < lim: yield f
else: break
p1 = p2
const N = 10_000
var result = toSeq(frobenius(10_000))
echo "Found $1 Frobenius numbers less than $2:".format(result.len, N)
echo result.join(" ")</syntaxhighlight>
{{out}}
<pre>Found 25 Frobenius numbers less than 10000:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599</pre>
=={{header|Perl}}==
{{libheader|ntheory}}
<
use warnings;
use feature 'say';
Line 598 ⟶ 1,255:
# process a list with a 2-wide sliding window
my $limit = 10_000;
say "\n" . join ' ', grep { $_ < $limit } slide { $a * $b - $a - $b } @{primes($limit)};</
{{out}}
<pre>25 matching numbers:
Line 606 ⟶ 1,263:
=={{header|Phix}}==
<!--<
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">4</span> <span style="color: #008080;">to</span> <span style="color: #000000;">6</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span>
Line 622 ⟶ 1,279:
<span style="color: #0000FF;">{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">frob</span><span style="color: #0000FF;">),</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">frob</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">),</span><span style="color: #008000;">", "</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
<pre>
Line 628 ⟶ 1,285:
167 Frobenius numbers under 1,000,000: 1, 7, 23, 59, 119, ..., 937019, 946719, 958431, 972179, 986039
</pre>
=={{header|Python}}==
<syntaxhighlight lang="python">
#!/usr/bin/python
def isPrime(v):
if v <= 1:
return False
if v < 4:
return True
if v % 2 == 0:
return False
if v < 9:
return True
if v % 3 == 0:
return False
else:
r = round(pow(v,0.5))
f = 5
while f <= r:
if v % f == 0 or v % (f + 2) == 0:
return False
f += 6
return True
pn = 2
n = 0
for i in range(3, 9999, 2):
if isPrime(i):
n += 1
f = (pn * i) - pn - i
if f > 10000:
break
print (n, ' => ', f)
pn = i
</syntaxhighlight>
=={{header|PL/M}}==
<syntaxhighlight lang="plm">100H:
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT;
PRINT: PROCEDURE (S); DECLARE S ADDRESS; CALL BDOS(9,S); END PRINT;
DECLARE LIMIT LITERALLY '10$000';
PRINT$NUMBER: PROCEDURE (N);
DECLARE S (8) BYTE INITIAL ('.....',13,10,'$');
DECLARE (N, P) ADDRESS, C BASED P BYTE;
P = .S(5);
DIGIT:
P = P - 1;
C = N MOD 10 + '0';
N = N / 10;
IF N > 0 THEN GO TO DIGIT;
CALL PRINT(P);
END PRINT$NUMBER;
SQRT: PROCEDURE (N) ADDRESS;
DECLARE (N, X0, X1) ADDRESS;
IF N <= 1 THEN RETURN 1;
X0 = SHR(N,1);
LOOP:
X1 = SHR(X0 + N/X0, 1);
IF X1 >= X0 THEN RETURN X0;
X0 = X1;
GO TO LOOP;
END SQRT;
SIEVE: PROCEDURE (LIM, BASE) ADDRESS;
DECLARE (LIM, BASE) ADDRESS;
DECLARE PRIMES BASED BASE ADDRESS;
DECLARE COUNT ADDRESS;
DECLARE SBASE ADDRESS, SIEVE BASED SBASE BYTE;
DECLARE (I, J, SQLIM) ADDRESS;
SBASE = BASE + LIM;
SQLIM = SQRT(LIM);
DO I=2 TO LIM;
SIEVE(I) = 1;
END;
DO I=2 TO SQLIM;
IF SIEVE(I) THEN DO;
DO J=I+I TO LIM BY I;
SIEVE(J) = 0;
END;
END;
END;
COUNT = 0;
DO I=2 TO LIM;
IF SIEVE(I) THEN DO;
PRIMES(COUNT) = I;
COUNT = COUNT+1;
END;
END;
RETURN COUNT;
END SIEVE;
FROBENIUS: PROCEDURE (N, PBASE) ADDRESS;
DECLARE (PBASE, N, P BASED PBASE) ADDRESS;
RETURN P(N) * P(N+1) - P(N) - P(N+1);
END FROBENIUS;
DECLARE NPRIMES ADDRESS;
DECLARE N ADDRESS;
NPRIMES = SIEVE(SQRT(LIMIT)+1, .MEMORY);
DO N=0 TO NPRIMES-2;
CALL PRINT$NUMBER(FROBENIUS(N, .MEMORY));
END;
CALL EXIT;
EOF</syntaxhighlight>
{{out}}
<pre>1
7
23
59
119
191
287
395
615
839
1079
1439
1679
1931
2391
3015
3479
3959
4619
5039
5615
6395
7215
8447
9599</pre>
=={{header|PureBasic}}==
<syntaxhighlight lang="purebasic">
Procedure isPrime(v.i)
If v < = 1 : ProcedureReturn #False
ElseIf v < 4 : ProcedureReturn #True
ElseIf v % 2 = 0 : ProcedureReturn #False
ElseIf v < 9 : ProcedureReturn #True
ElseIf v % 3 = 0 : ProcedureReturn #False
Else
Protected r = Round(Sqr(v), #PB_Round_Down)
Protected f = 5
While f <= r
If v % f = 0 Or v % (f + 2) = 0
ProcedureReturn #False
EndIf
f + 6
Wend
EndIf
ProcedureReturn #True
EndProcedure
OpenConsole()
pn.i = 2
n.i = 0
For i.i = 3 To 9999 Step 2
If isPrime(i)
n + 1
f.i = pn * i - pn - i
If f > 10000
Break
EndIf
Print(Str(n) + " => " + Str(f) + #CRLF$)
pn = i
EndIf
Next i
Input()
CloseConsole()
End
</syntaxhighlight>
{{out}}
<pre>
1 => 1
2 => 7
3 => 23
4 => 59
5 => 119
6 => 191
7 => 287
8 => 395
9 => 615
10 => 839
11 => 1079
12 => 1439
13 => 1679
14 => 1931
15 => 2391
16 => 3015
17 => 3479
18 => 3959
19 => 4619
20 => 5039
21 => 5615
22 => 6395
23 => 7215
24 => 8447
25 => 9599
</pre>
=={{header|Quackery}}==
<code>eratosthenes</code> and <code>isprime</code> are defined at [[Sieve of Eratosthenes#Quackery]].
In this solution the primes and Frobenius numbers are zero indexed rather than one indexed as per the task. It simplifies the code a smidgeon, as Quackery nests are zero indexed.
<syntaxhighlight lang="Quackery"> 200 eratosthenes
[ [ [] 200 times
[ i^ isprime if
[ i^ join ] ] ]
constant
swap peek ] is prime ( n --> n )
[ dup prime
swap 1+ prime
2dup * rot - swap - ] is frobenius ( n --> n )
[] 0
[ tuck frobenius dup
10000 < while
join swap
1+ again ]
drop nip echo </syntaxhighlight>
{{out}}
<pre>[ 1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599 ]</pre>
=={{header|Raku}}==
<syntaxhighlight lang="raku"
given (^1000).grep( *.is-prime ).rotor(2 => -1)
.map( { (.[0] * .[1] - .[0] - .[1]) } ).grep(* < 10000);</
{{out}}
<pre>25 matching numbers
Line 640 ⟶ 1,534:
=={{header|REXX}}==
<
parse arg hi cols . /*obtain optional argument from the CL.*/
if hi=='' | hi=="," then hi= 10000 /* " " " " " " */
if cols=='' | cols=="," then cols= 10 /* " " " " " " */
w= 10 /*the width of any column in the output*/
call genP /*build array of semaphores for primes.*/
if cols>0 then say ' index │'center(
if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─')
$=; idx= 1 /*list of Frobenius #s (so far); index.*/
do j=1; jp= j+1; y= @.j*@.jp - @.j - @.jp /*calculate a Frobenius number. */
if y>= hi then leave /*Is Y too high? Yes, then leave. */
if cols
c= commas(y) /*maybe add commas to the number. */
$= $ right(c, max(w, length(c) ) )
if j//cols\==0 then iterate /*have we populated a line of output? */
say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */
Line 660 ⟶ 1,555:
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(j-1)
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
Line 668 ⟶ 1,563:
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6= 13 /*define some low primes. */
/* [↓] generate more primes ≤ high.*/
do j=@.#+
if j//7==0 then
do k=6 while sq.k<=j
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j;
end /*j*/; return</
{{out|output|text= when using the default inputs:}}
<pre>
Line 694 ⟶ 1,586:
=={{header|Ring}}==
<syntaxhighlight lang="ring">load "stdlib.ring" # for isprime() function
? "working..." + nl + "Frobenius numbers are:"
# create table of prime numbers between
Frob = [2]
for n = 3 to
if isprime(n) Add(Frob,n) ok
next
Line 712 ⟶ 1,603:
next
? nl + nl + "Found " + (m-1) + " Frobenius numbers" + nl + "done..."
# a very plain string formatter, intended to even up columnar outputs
Line 718 ⟶ 1,609:
s = string(x) l = len(s)
if l > y y = l ok
return substr(" ", 11 - y + l) + s</
{{out}}
<pre>working...
Frobenius numbers are:
1 7 23 59 119
191 287 395 615 839
1079 1439 1679 1931 2391
3015 3479 3959 4619 5039
5615 6395 7215 8447 9599
Found 25 Frobenius numbers
done...</pre>
=={{header|RPL}}==
« → max
« { } 2 OVER
'''DO'''
ROT SWAP + SWAP
DUP NEXTPRIME DUP2 * OVER - ROT -
'''UNTIL''' DUP max ≥ '''END'''
DROP2
» » ‘<span style="color:blue>FROB</span>’ STO
10000 <span style="color:blue>FROB</span>
{{out}}
<pre>
1: { 1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599 }
</pre>
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">require 'prime'
Prime.each_cons(2) do |p1, p2|
f = p1*p2-p1-p2
break if f > 10_000
puts f
end
</syntaxhighlight>
{{out}}
<pre>1
7
23
59
119
191
287
395
615
839
1079
1439
1679
1931
2391
3015
3479
3959
4619
5039
5615
6395
7215
8447
9599
</pre>
=={{header|Rust}}==
<
// primal = "0.3"
Line 762 ⟶ 1,707:
}
println!();
}</
{{out}}
Line 784 ⟶ 1,729:
770879 776159* 781451 802715 824459* 835379* 851903 868607 879839* 889239
900591 919631* 937019 946719 958431 972179 986039
</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func frobenius_number(n) {
prime(n) * prime(n+1) - prime(n) - prime(n+1)
}
say gather {
1..Inf -> each {|k|
var n = frobenius_number(k)
break if (n >= 10_000)
take(n)
}
}</syntaxhighlight>
{{out}}
<pre>
[1, 7, 23, 59, 119, 191, 287, 395, 615, 839, 1079, 1439, 1679, 1931, 2391, 3015, 3479, 3959, 4619, 5039, 5615, 6395, 7215, 8447, 9599]
</pre>
=={{header|Wren}}==
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<
import "./
var primes = Int.primeSieve(101)
Line 802 ⟶ 1,762:
}
System.print("Frobenius numbers under 10,000:")
Fmt.tprint("$,5d", frobenius, 9)
System.print("\n%(frobenius.count) such numbers found.")</
{{out}}
Line 813 ⟶ 1,773:
25 such numbers found.
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang="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;
];
int Count, M, Pn, Pn1, F;
[Count:= 0;
M:= 2; \first prime
Pn:= M;
loop [repeat M:= M+1 until IsPrime(M);
Pn1:= M;
F:= Pn*Pn1 - Pn - Pn1;
if F >= 10_000 then quit;
IntOut(0, F);
Count:= Count+1;
if rem(Count/10) = 0 then CrLf(0) else ChOut(0, 9\tab\);
Pn:= Pn1;
];
CrLf(0);
IntOut(0, Count);
Text(0, " Frobenius numbers found below 10,000.
");
]</syntaxhighlight>
{{out}}
<pre>
1 7 23 59 119 191 287 395 615 839
1079 1439 1679 1931 2391 3015 3479 3959 4619 5039
5615 6395 7215 8447 9599
25 Frobenius numbers found below 10,000.
</pre>
=={{header|Yabasic}}==
{{trans|PureBasic}}
<syntaxhighlight lang="yabasic">
sub isPrime(v)
if v < 2 then return False : fi
if mod(v, 2) = 0 then return v = 2 : fi
if mod(v, 3) = 0 then return v = 3 : fi
d = 5
while d * d <= v
if mod(v, d) = 0 then return False else d = d + 2 : fi
wend
return True
end sub
pn = 2
n = 0
for i = 3 to 9999 step 2
if isPrime(i) then
n = n + 1
f = pn * i - pn - i
if f > 10000 then break : fi
print n, " => ", f
pn = i
end if
next i
end
</syntaxhighlight>
{{out}}
<pre>
Igual que la entrada de PureBasic.
</pre>
| |||