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
page 37
ANTLRInputStream input = new ANTLRInputStream(is);
as of ANTLR 4 .8 should be:
CharStream stream = CharStreams.fromStream(i...
New
Python Testing With Pytest - Chapter 2, warnings for “unregistered custom marks”
While running the smoke tests in Chapter 2, I get these...
New
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
I ran this command after installing the sample application:
$ cards add do something --owner Brian
And got a file not found error:
Fil...
New
I’m running Android Studio “Arctic Fox” 2020.3.1 Patch 2, and I’m embarrassed to admit that I only made it to page 8 before running into ...
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
Hi,
I am getting an error I cannot figure out on my test.
I have what I think is the exact code from the book, other than I changed “us...
New
Hi, I’m working on the Chapter 8 of the book.
After I add add the point_offset, I’m still able to see acne:
In the image above, I re...
New
Getting an error when installing the dependencies at the start of this chapter:
could not compile dependency :exla, "mix compile" failed...
New
@mfazio23
Android Studio will not accept anything I do when trying to use the Transformations class, as described on pp. 140-141. Googl...
New
Other popular topics
Which, if any, games do you play? On what platform?
I just bought (and completed) Minecraft Dungeons for my Nintendo Switch. Other than ...
New
No chair. I have a standing desk.
This post was split into a dedicated thread from our thread about chairs :slight_smile:
New
Design and develop sophisticated 2D games that are as much fun to make as they are to play. From particle effects and pathfinding to soci...
New
You might be thinking we should just ask who’s not using VSCode :joy: however there are some new additions in the space that might give V...
New
The V Programming Language
Simple language for building maintainable programs
V is already mentioned couple of times in the forum, but I...
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
Jamis Buck
@jamis
This month, we have the pleasure of spotlighting author Jamis Buck, who has written Mazes for Prog...
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
I have always used antique keyboards like Cherry MX 1800 or Cherry MX 8100 and almost always have modified the switches in some way, like...
New
Ok, well here are some thoughts and opinions on some of the ergonomic keyboards I have, I guess like mini review of each that I use enoug...
New
Categories:
Sub Categories:
Popular Portals
- /elixir
- /rust
- /ruby
- /wasm
- /erlang
- /phoenix
- /keyboards
- /python
- /js
- /rails
- /security
- /go
- /swift
- /vim
- /clojure
- /emacs
- /haskell
- /java
- /svelte
- /onivim
- /typescript
- /kotlin
- /crystal
- /c-plus-plus
- /tailwind
- /react
- /gleam
- /ocaml
- /elm
- /flutter
- /vscode
- /ash
- /html
- /opensuse
- /centos
- /zig
- /deepseek
- /php
- /scala
- /react-native
- /textmate
- /lisp
- /sublime-text
- /debian
- /nixos
- /agda
- /django
- /kubuntu
- /arch-linux
- /deno
- /ubuntu
- /revery
- /nodejs
- /spring
- /manjaro
- /lua
- /diversity
- /julia
- /markdown
- /c








