
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 topics

Some minor things in the paper edition that says “3 2020” on the title page verso, not mentioned in the book’s errata online:
p. 186 But...
New

Running the examples in chapter 5 c under pytest 5.4.1 causes an AttributeError: ‘module’ object has no attribute ‘config’.
In particula...
New

Hi Brian,
Looks like the api for tinydb has changed a little. Noticed while working on chapter 7 that the .purge() call to the db throws...
New

The following is cross-posted from the original Ray Tracer Challenge forum, from a post by garfieldnate. I’m cross-posting it so that the...
New

I am working on the “Your Turn” for chapter one and building out the restart button talked about on page 27. It recommends looking into ...
New

Hello! Thanks for the great book.
I was attempting the Trie (chap 17) exercises and for number 4 the solution provided for the autocorre...
New

This is as much a suggestion as a question, as a note for others.
Locally the SGP30 wasn’t available, so I ordered a SGP40. On page 53, ...
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

@parrt
In the context of Chapter 4.3, the grammar Java.g4, meant to parse Java 6 compilation units, no longer passes ANTLR (currently 4....
New

Hello @herbert ! Trying to get the very first “Hello, Bracket Terminal!" example to run (p. 53). I develop on an Amazon EC2 instance runn...
New
Other popular topics

What chair do you have while working… and why?
Is there a ‘best’ type of chair or working position for developers?
New

My first contact with Erlang was about 2 years ago when I used RabbitMQ, which is written in Erlang, for my job. This made me curious and...
New

We have a thread about the keyboards we have, but what about nice keyboards we come across that we want? If you have seen any that look n...
New

Rust is an exciting new programming language combining the power of C with memory safety, fearless concurrency, and productivity boosters...
New

Biggest jackpot ever apparently! :upside_down_face:
I don’t (usually) gamble/play the lottery, but working on a program to predict the...
New

Author Spotlight
Dmitry Zinoviev
@aqsaqal
Today we’re putting our spotlight on Dmitry Zinoviev, author of Data Science Essentials in ...
New

The File System Access API with Origin Private File System.
WebKit supports new API that makes it possible for web apps to create, open,...
New

Author Spotlight:
Sophie DeBenedetto
@SophieDeBenedetto
The days of the traditional request-response web application are long gone, b...
New

Will Swifties’ war on AI fakes spark a deepfake porn reckoning?
New

This is a very quick guide, you just need to:
Download LM Studio: https://lmstudio.ai/
Click on search
Type DeepSeek, then select the o...
New
Latest in PragProg
Latest (all)
Categories:
Popular Portals
- /elixir
- /rust
- /wasm
- /ruby
- /erlang
- /phoenix
- /keyboards
- /js
- /rails
- /python
- /security
- /go
- /swift
- /vim
- /clojure
- /java
- /haskell
- /emacs
- /svelte
- /onivim
- /typescript
- /crystal
- /c-plus-plus
- /tailwind
- /kotlin
- /gleam
- /react
- /flutter
- /elm
- /ocaml
- /vscode
- /opensuse
- /ash
- /centos
- /php
- /deepseek
- /scala
- /zig
- /html
- /debian
- /nixos
- /lisp
- /agda
- /react-native
- /textmate
- /sublime-text
- /kubuntu
- /arch-linux
- /revery
- /ubuntu
- /manjaro
- /spring
- /django
- /diversity
- /nodejs
- /lua
- /slackware
- /julia
- /c
- /neovim