Frobenius numbers: Difference between revisions
Add BCPL
(Added C++ solution) |
Not a robot (talk | contribs) (Add BCPL) |
||
Line 89:
Frobenius numbers 3-9999: 25
</pre>
=={{header|BCPL}}==
<lang bcpl>get "libhdr"
manifest $( limit = 10000 $)
// Integer square root
let sqrt(s) =
s <= 1 -> 1,
valof
$( let x0 = s >> 1
let x1 = (x0 + s/x0) >> 1
while x1 < x0
$( x0 := x1
x1 := (x0 + s/x0) >> 1
$)
resultis x0
$)
// Find primes up to n, store at v.
// Returns amount of primes found
let sieve(v, n) = valof
$( let count = 0
// Sieve the primes
for i=2 to n do v!i := true
for i=2 to sqrt(n)
if v!i then
$( let j = i+i
while j <= n
$( v!j := false
j := j + i
$)
$)
// Filter the primes
for i=2 to n
if v!i then
$( v!count := i
count := count + 1
$)
resultis count
$)
// Frobenius number given prime array
let frob(p, n) = p!n * p!(n+1) - p!n - p!(n+1)
let start() be
$( // frob(n) is always less than p(n+1)^2
// sieving up to the square root of the limit is enough,
// though whe need one extra since p(n+1) is necessary
let primes = getvec(sqrt(limit)+1)
let nprimes = sieve(primes, sqrt(limit)+1)
// similarly, having found that many primes, we generate
// one fewer Frobenius number
for n = 0 to nprimes-2 do
writef("%N*N", frob(primes, n))
freevec(primes)
$)</lang>
{{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|C#|CSharp}}==
| |||