Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Enumerate the primes using only unary arithmetic
interface NaturalNumber {}
class Zero implements NaturalNumber {
@Override
public String toString() {
return "0";
}
}
class Successor implements NaturalNumber {
final NaturalNumber prev;
Successor(NaturalNumber prev) {
this.prev = prev;
}
@Override
public String toString() {
return String.format("S(%s)", prev);
}
}
class Primes {
static boolean isGreater(NaturalNumber a, NaturalNumber b) {
while (a instanceof Successor && b instanceof Successor) {
a = ((Successor) a).prev;
b = ((Successor) b).prev;
}
return a instanceof Successor;
}
static NaturalNumber difference(NaturalNumber a, NaturalNumber b) {
if (isGreater(b, a))
throw new IllegalArgumentException("Second operand was greater than first.");
while (b instanceof Successor) {
a = ((Successor) a).prev;
b = ((Successor) b).prev;
}
return a;
}
static NaturalNumber remainder(NaturalNumber a, NaturalNumber b) {
while (!isGreater(b, a))
a = difference(a, b);
return a;
}
static boolean isDivisible(NaturalNumber a, NaturalNumber b) {
return remainder(a, b) instanceof Zero;
}
static boolean isPrime(NaturalNumber n) {
if (n instanceof Zero || ((Successor) n).prev instanceof Zero)
return false;
NaturalNumber d = new Successor(new Successor(new Zero()));
while (isGreater(n, d)) {
if (isDivisible(n, d))
return false;
d = new Successor(d);
}
return true;
}
public static void main(String[] args) {
for (NaturalNumber n = new Zero();; n = new Successor(n))
if (isPrime(n))
System.out.println(n);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.