dtonhofer
Functional Programming in Java, Second Edition: p.135 code for "primes" using a self-modifying filter
This is no particular interest but here is some code that uses the “execute around” pattern to build a timer to time the “primes generator”, as well as a second primes generator that uses a self-modifying stream filter, a closure that accumulates all the primes found so far so as to perform divisibility testing, which is evidently faster than the “try to divide by every x between 2 and sqrt(n)”.
import org.junit.jupiter.api.Test;
import java.util.*;
import java.util.function.Predicate;
import java.util.function.Supplier;
import java.util.stream.IntStream;
import java.util.stream.Stream;
import static java.util.stream.Collectors.toList;
import static org.junit.jupiter.api.Assertions.assertEquals;
class SimpleTimer {
public final long duration_ms;
public final List<Integer> result;
private SimpleTimer(List<Integer> result, long duration_ms) {
this.result = Collections.unmodifiableList(result);
this.duration_ms = duration_ms;
}
public static SimpleTimer timeIt(Supplier<List<Integer>> supplier) {
long start = System.currentTimeMillis();
List<Integer> result = supplier.get();
long stop = System.currentTimeMillis();
return new SimpleTimer(result, stop - start);
}
}
class Primes {
public static boolean isPrime(final int number) {
return number > 1 &&
IntStream.rangeClosed(2, (int) Math.sqrt(number))
.noneMatch(divisor -> number % divisor == 0);
}
private static int primeAfter(final int number) {
if (isPrime(number + 1)) {
return number + 1;
}
return primeAfter(number + 1);
}
public static List<Integer> primes(final int fromNumber, final int count) {
return Stream.iterate(primeAfter(fromNumber - 1), Primes::primeAfter)
.limit(count)
.collect(toList());
}
}
class PrimesSieveNoDoubles {
private enum What {found_divisor, surpassed_sqrt, possibly_prime}
// This is actually a little bit *slower* than a version that computes sqrt(x)
// to determine whether to stop instead of using integer division to check whether
// the dividend has become smaller than the divisor.
public static List<Integer> primes(int limit) {
final var store = new LinkedList<Integer>();
Predicate<Integer> p = x -> {
What what = What.possibly_prime;
Iterator<Integer> iter = store.iterator();
while (what == What.possibly_prime && iter.hasNext()) {
int somePrime = iter.next();
// it is faster to compute remainder and divisor next to one another always
// than compute the divisor inside the "else", apparently due to compiler optimizations
int remainder = x % somePrime;
int dividend = x / somePrime;
if (remainder == 0) {
// System.out.println(x + " = " + somePrime + "*n, not a prime");
what = What.found_divisor;
} else {
// int divisor = x / somePrime;
if (dividend < somePrime) {
what = What.surpassed_sqrt;
}
}
}
if (what == What.surpassed_sqrt || what == What.possibly_prime) {
// System.out.println(x + " is prime");
store.addLast(x);
return true;
} else {
return false;
}
};
List<Integer> result = Stream.iterate(2, x -> x + 1).
filter(p).
limit(limit).
collect(toList());
// add the end of the collect, the result and the store have the same content
// this comparison takes a few ms
assertEquals(store,result);
return result;
}
}
public class Primality {
private final static int limit = 1_000_000;
@Test
void runBookPrimes() {
List<Integer> l1 = Primes.primes(1, 10);
List<Integer> l2 = Primes.primes(100, 5);
assertEquals(List.of(2, 3, 5, 7, 11, 13, 17, 19, 23, 29),l1);
assertEquals(List.of(101, 103, 107, 109, 113),l2);
System.out.println("10 primes from 1: " + l1);
System.out.println("5 primes from 100: " + l2);
}
@Test
void runBookPrimesWithTimer() {
// not an actual test, just printout
final SimpleTimer timeIt = SimpleTimer.timeIt(() -> Primes.primes(2, limit));
final List<Integer> result = timeIt.result;
final String range = (result.isEmpty()) ? "" : "in range [" + result.get(0) + "," + result.get(result.size() - 1) + "] ";
System.out.println("Using book code: finding " + result.size() + " primes " + range + "took " + timeIt.duration_ms + " ms");
}
@Test
void runPrimesSieveWithTimer() {
// not an actual test, just printout
final SimpleTimer timeIt = SimpleTimer.timeIt(() -> PrimesSieveNoDoubles.primes(limit));
final List<Integer> result = timeIt.result;
final String range = (result.isEmpty()) ? "" : "in range [" + result.get(0) + "," + result.get(result.size() - 1) + "] ";
System.out.println("Using primes sieve w/o doubles: finding " + result.size() + " primes " + range + "took " + timeIt.duration_ms + " ms");
}
}
Popular Pragmatic Bookshelf topics
I can’t setup the Rails source code. This happens in a working directory containing multiple (postgres) Rails apps.
With:
ruby-3.0.0
s...
New
Title: Intuitive Python: docker run… denied error (page 2)
Attempted to run the docker command in both CLI and Powershell
PS C:\Users\r...
New
The book has the same “Problem space/Solution space” diagram on page 18 as is on page 17. The correct Problem/Solution space diagrams ar...
New
I’m under the impression that when the reader gets to page 136 (“View Data with the Database Inspector”), the code SHOULD be able to buil...
New
In general, the book isn’t yet updated for Phoenix version 1.6. On page 18 of the book, the authors indicate that an auto generated of ro...
New
When installing Cards as an editable package, I get the following error:
ERROR: File “setup.py” not found. Directory cannot be installe...
New
Hi, I’ve got a question about the implementation of PubSub when using a Phoenix.Socket.Transport behaviour rather than channels.
Before ...
New
AWDWR 7, page 152, page 153:
Hello everyone,
I’m a little bit lost on the hotwire part. I didn’t fully understand it.
On page 152 @rub...
New
Docker-Machine became part of the Docker Toolbox, which was deprecated in 2020, long after Docker Desktop supported Docker Engine nativel...
New
I’ve got to the end of Ch. 11, and the app runs, with all tabs displaying what they should – at first. After switching around between St...
New
Other popular topics
Write Elixir tests that you can be proud of. Dive into Elixir’s test philosophy and gain mastery over the terminology and concepts that u...
New
What chair do you have while working… and why?
Is there a ‘best’ type of chair or working position for developers?
New
New
Hi folks,
I don’t know if I saw this here but, here’s a new programming language, called Roc
Reminds me a bit of Elm and thus Haskell. ...
New
If you get Can't find emacs in your PATH when trying to install Doom Emacs on your Mac you… just… need to install Emacs first! :lol:
bre...
New
Author Spotlight
Erin Dees
@undees
Welcome to our new author spotlight! We had the pleasure of chatting with Erin Dees, co-author of ...
New
There appears to have been an update that has changed the terminology for what has previously been known as the Taskbar Overflow - this h...
New
zig/http.zig at 7cf2cbb33ef34c1d211135f56d30fe23b6cacd42 · ziglang/zig.
General-purpose programming language and toolchain for maintaini...
New
Jan | Rethink the Computer.
Jan turns your computer into an AI machine by running LLMs locally on your computer. It’s a privacy-focus, l...
New
Develop, deploy, and debug BEAM applications using BEAMOps: a new paradigm that focuses on scalability, fault tolerance, and owning each ...
New
Categories:
Sub Categories:
Popular Portals
- /elixir
- /rust
- /ruby
- /wasm
- /erlang
- /phoenix
- /keyboards
- /python
- /js
- /rails
- /security
- /go
- /swift
- /vim
- /clojure
- /java
- /emacs
- /haskell
- /svelte
- /onivim
- /typescript
- /kotlin
- /c-plus-plus
- /crystal
- /tailwind
- /react
- /gleam
- /ocaml
- /elm
- /flutter
- /vscode
- /ash
- /html
- /opensuse
- /zig
- /centos
- /deepseek
- /php
- /scala
- /lisp
- /react-native
- /textmate
- /sublime-text
- /nixos
- /debian
- /agda
- /django
- /kubuntu
- /deno
- /arch-linux
- /nodejs
- /revery
- /ubuntu
- /spring
- /manjaro
- /diversity
- /lua
- /markdown
- /julia
- /slackware








