From: Rolf Eike Beer <eike@sf-mail.de>
To: gentoo-dev@lists.gentoo.org
Subject: [gentoo-dev] [PATCH 3/3] qmail.eclass: simplify is_prime()
Date: Thu, 12 Aug 2021 17:25:55 +0200 [thread overview]
Message-ID: <12828076.uLZWGnKmhe@eto.sf-tec.de> (raw)
In-Reply-To: <4644122.GXAFRqVoOG@eto.sf-tec.de>
[-- Attachment #1: Type: text/plain, Size: 3166 bytes --]
The previous algorithm would scan for all primes for a given number, which
takes needlessly long.
Signed-off-by: Rolf Eike Beer <eike@sf-mail.de>
---
eclass/qmail.eclass | 51 +++++++++++++++---------------------------
eclass/tests/qmail.sh | 52 +++++++++++++++++++++++++++++++++++++++++++
2 files changed, 70 insertions(+), 33 deletions(-)
create mode 100755 eclass/tests/qmail.sh
diff --git a/eclass/qmail.eclass b/eclass/qmail.eclass
index 40130a502cb..9f644dd74c8 100644
--- a/eclass/qmail.eclass
+++ b/eclass/qmail.eclass
@@ -29,46 +29,31 @@ GENQMAIL_S="${WORKDIR}"/genqmail-${GENQMAIL_PV}
QMAIL_SPP_F=qmail-spp-${QMAIL_SPP_PV}.tar.gz
QMAIL_SPP_S="${WORKDIR}"/qmail-spp-${QMAIL_SPP_PV}
-# @FUNCTION: primes
-# @USAGE: <min> <max>
+# @FUNCTION: is_prime
+# @USAGE: <number>
# @DESCRIPTION:
-# Prints a list of primes between min and max inclusive
-# Note: this functions gets very slow when used with large numbers.
-primes() {
- local min=${1} max=${2}
- local result= primelist=2 i p
+# Checks wether a number is a valid prime number for queue split
+is_prime() {
+ local number=${1} i
+
+ if [[ ${number} -lt 7 ]]; then
+ # too small
+ return 1
+ fi
- [[ ${min} -le 2 ]] && result="${result} 2"
+ if [[ $[number % 2] == 0 ]]; then
+ return 1
+ fi
- for ((i = 3; i <= max; i += 2))
+ # let i run up to the square root of number
+ for ((i = 3; i * i <= number; i += 2))
do
- for p in ${primelist}
- do
- [[ $[i % p] == 0 || $[p * p] -gt ${i} ]] && \
- break
- done
- if [[ $[i % p] != 0 ]]
- then
- primelist="${primelist} ${i}"
- [[ ${i} -ge ${min} ]] && \
- result="${result} ${i}"
+ if [[ $[number % i ] == 0 ]]; then
+ return 1
fi
done
- echo ${result}
-}
-
-# @FUNCTION: is_prima
-# @USAGE: <number>
-# @DESCRIPTION:
-# Checks wether a number is a prime number
-is_prime() {
- local number=${1} i
- for i in $(primes ${number} ${number})
- do
- [[ ${i} == ${number} ]] && return 0
- done
- return 1
+ return 0
}
dospp() {
diff --git a/eclass/tests/qmail.sh b/eclass/tests/qmail.sh
new file mode 100755
index 00000000000..3520ed2a9d5
--- /dev/null
+++ b/eclass/tests/qmail.sh
@@ -0,0 +1,52 @@
+#!/bin/bash
+# Copyright 2020-2021 Gentoo Authors
+# Distributed under the terms of the GNU General Public License v2
+
+EAPI=8
+source tests-common.sh
+
+inherit qmail
+
+# some numbers are blocked because they are to small even if prime
+test_low_numbers() {
+ tbegin "low numbers"
+
+ for i in $(seq 0 6); do
+ if is_prime ${i}; then
+ return tend 1 "${i} badly accepted"
+ fi
+ done
+
+ tend 0
+}
+
+# test a given number for being prime
+check_prime_number() {
+ # use factor from coreutils to count the factors
+ if [[ $(factor $1 | cut -d: -f2 | wc -w) == 1 ]]; then
+ return $(is_prime $1)
+ else
+ return $(is_prime $1 && false || true)
+ fi
+}
+
+test_primes() {
+ tbegin "factorizations from ${1} to ${2}"
+
+ for i in $(seq ${1:?} ${2:?}); do
+ if ! check_prime_number $i; then
+ tend 1 "${i} returned bad factorization"
+ return 1
+ fi
+ done
+
+ tend 0
+}
+
+test_low_numbers
+test_primes 7 99
+for i in $(seq 100 100 1000); do
+ test_primes $i $((i + 99))
+done
+
+texit
--
2.26.2
[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 195 bytes --]
next prev parent reply other threads:[~2021-08-12 15:26 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-08-12 9:54 [gentoo-dev] [PATCH 1/3] qmail.eclass: support EAPI 8 Rolf Eike Beer
2021-08-12 9:55 ` [gentoo-dev] [PATCH 2/3] qmail.eclass: hardcode root group Rolf Eike Beer
2021-08-12 11:13 ` Ulrich Mueller
2021-08-12 14:03 ` Rolf Eike Beer
2021-08-12 15:22 ` [gentoo-dev] [PATCH 2/3] qmail.eclass: remove magic to query " Rolf Eike Beer
2021-08-12 17:39 ` Michael Orlitzky
2021-08-13 7:17 ` Rolf Eike Beer
2021-08-13 9:06 ` Ulrich Mueller
2021-08-13 10:31 ` Rolf Eike Beer
2021-08-14 10:43 ` David Seifert
2021-08-14 9:36 ` [gentoo-dev] [PATCH 2/3 v3] " Rolf Eike Beer
2021-08-14 10:52 ` Ulrich Mueller
2021-08-14 11:11 ` Rolf Eike Beer
2021-08-14 11:54 ` Ulrich Mueller
2021-08-14 11:34 ` [gentoo-dev] [PATCH 2/3 v4] " Rolf Eike Beer
2021-08-12 9:55 ` [gentoo-dev] [PATCH 3/5] qmail.eclass: simplify is_prime() Rolf Eike Beer
2021-08-12 11:25 ` Ulrich Mueller
2021-08-12 15:25 ` Rolf Eike Beer
2021-08-12 15:25 ` Rolf Eike Beer [this message]
2021-08-13 7:47 ` [gentoo-dev] [PATCH 4/3] qmail.eclass: remove needless keepdirs Rolf Eike Beer
2021-08-14 11:47 ` [gentoo-dev] [PATCH 4/3 v2] " Rolf Eike Beer
2021-08-13 10:44 ` [gentoo-dev] [PATCH 5/3] qmail.eclass: retire qmail_tcprules_fixup() Rolf Eike Beer
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=12828076.uLZWGnKmhe@eto.sf-tec.de \
--to=eike@sf-mail.de \
--cc=gentoo-dev@lists.gentoo.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox