
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

This test is broken right out of the box…
— FAIL: TestAgent (7.82s)
agent_test.go:77:
Error Trace: agent_test.go:77
agent_test.go:...
New

Many tasks_proj/tests directories exist in chapters 2, 3, 5 that have tests that use the custom markers smoke and get, which are not decl...
New

When I try the command to create a pair of migration files I get an error.
user=> (create-migration "guestbook")
Execution error (Ill...
New

Hi @Margaret ,
On page VII the book tells us the example and snippets will be all using Elixir version 1.11
But on page 3 almost the en...
New

Title: Web Development with Clojure, Third Edition, vB17.0 (p9)
The create table guestbook syntax suggested doesn’t seem to be accepted ...
New

Dear Sophie.
I tried to do the “Authorization” exercise and have two questions:
When trying to plug in an email-service, I found the ...
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 have just acquired Michael Fazio’s “Kotlin and Android Development” to learn about game programming for Android. I have a game in p...
New

When installing Cards as an editable package, I get the following error:
ERROR: File “setup.py” not found. Directory cannot be installe...
New

@mfazio23
I’ve applied the changes from Chapter 5 of the book and everything builds correctly and runs. But, when I try to start a game,...
New
Other popular topics

Hello Devtalk World!
Please let us know a little about who you are and where you’re from :nerd_face:
New

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

Build highly interactive applications without ever leaving Elixir, the way the experts do. Let LiveView take care of performance, scalabi...
New

Author Spotlight
Mike Riley
@mriley
This month, we turn the spotlight on Mike Riley, author of Portable Python Projects. Mike’s book ...
New

Author Spotlight:
Karl Stolley
@karlstolley
Logic! Rhetoric! Prag! Wow, what a combination. In this spotlight, we sit down with Karl ...
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

A Brief Review of the Minisforum V3 AMD Tablet.
Update: I have created an awesome-minisforum-v3 GitHub repository to list information fo...
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

Fight complexity and reclaim the original spirit of agility by learning to simplify how you develop software. The result: a more humane a...
New
Categories:
Sub Categories:
Popular Portals
- /elixir
- /rust
- /wasm
- /ruby
- /erlang
- /phoenix
- /keyboards
- /rails
- /js
- /python
- /security
- /go
- /swift
- /vim
- /clojure
- /emacs
- /haskell
- /java
- /onivim
- /typescript
- /svelte
- /crystal
- /kotlin
- /c-plus-plus
- /tailwind
- /gleam
- /react
- /ocaml
- /flutter
- /elm
- /vscode
- /ash
- /opensuse
- /html
- /centos
- /php
- /deepseek
- /zig
- /scala
- /textmate
- /lisp
- /sublime-text
- /nixos
- /debian
- /react-native
- /agda
- /kubuntu
- /arch-linux
- /django
- /revery
- /ubuntu
- /spring
- /manjaro
- /nodejs
- /diversity
- /lua
- /julia
- /c
- /slackware
- /neovim