
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 Prag Prog topics

Python Testing With Pytest - Chapter 2, warnings for “unregistered custom marks”
While running the smoke tests in Chapter 2, I get these...
New

Title: Hands-On Rust (Chapter 11: prefab)
Just played a couple of amulet-less games. With a bit of debugging, I believe that your can_p...
New

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

In case this helps anyone, I’ve had issues setting up the rails source code. Here were the solutions:
In Gemfile, change
gem 'rails'
t...
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

The markup used to display the uploaded image results in a Phoenix.LiveView.HTMLTokenizer.ParseError error.
lib/pento_web/live/product_l...
New

When running the program in chapter 8, “Implementing Combat”, the printout Health before attack was never printed so I assumed something ...
New

Docker-Machine became part of the Docker Toolbox, which was deprecated in 2020, long after Docker Desktop supported Docker Engine nativel...
New

root_layout: {PentoWeb.LayoutView, :root},
This results in the following following error:
no “root” html template defined for PentoWeb...
New

From page 13:
On Python 3.7, you can install the libraries with pip by running these commands inside a Python venv using Visual Studio ...
New
Other popular topics

Any thoughts on Svelte?
Svelte is a radical new approach to building user interfaces. Whereas traditional frameworks like React and Vue...
New

I am a Linux user since 2012, more or less, and I always use Ubuntu on my computers, and my last 2 laptops have been used Thinkpads, wher...
New

Do the test and post your score :nerd_face:
:keyboard:
If possible, please add info such as the keyboard you’re using, the layout (Qw...
New

Crystal recently reached version 1. I had been following it for awhile but never got to really learn it. Most languages I picked up out o...
New

Here’s the story how one of the world’s first production deployments of LiveView came to be - and how trying to improve it almost caused ...
New

This is going to be a long an frequently posted thread.
While talking to a friend of mine who has taken data structure and algorithm cou...
New

We’ve talked about his book briefly here but it is quickly becoming obsolete - so he’s decided to create a series of 7 podcasts, the firs...
New

Was just curious to see if any were around, found this one:
I got 51/100:
Not sure if it was meant to buy I am sure at times the b...
New

Author Spotlight:
David Bryant Copeland
@davetron5000
We’re so happy to bring you another Author Spotlight, a series where we sit dow...
New

Inside our android webview app, we are trying to paste the copied content from another app eg (notes) using navigator.clipboard.readtext ...
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
- /textmate
- /sublime-text
- /react-native
- /kubuntu
- /arch-linux
- /revery
- /ubuntu
- /manjaro
- /django
- /spring
- /diversity
- /nodejs
- /lua
- /c
- /slackware
- /julia
- /neovim