[gentoo-commits] repo/gentoo:master commit in: eclass/, eclass/tests/

public inbox for gentoo-commits@lists.gentoo.org
 help / color / mirror / Atom feed

From: "Sam James" <sam@gentoo.org>
To: gentoo-commits@lists.gentoo.org
Subject: [gentoo-commits] repo/gentoo:master commit in: eclass/, eclass/tests/
Date: Tue, 17 Aug 2021 01:41:29 +0000 (UTC)	[thread overview]
Message-ID: <1629164477.6d0a5587e8f7d51544824fb7eb806ba5c4dcb4e7.sam@gentoo> (raw)

commit:     6d0a5587e8f7d51544824fb7eb806ba5c4dcb4e7
Author:     Rolf Eike Beer <eike <AT> sf-mail <DOT> de>
AuthorDate: Thu Jun 17 14:39:07 2021 +0000
Commit:     Sam James <sam <AT> gentoo <DOT> org>
CommitDate: Tue Aug 17 01:41:17 2021 +0000
URL:        https://gitweb.gentoo.org/repo/gentoo.git/commit/?id=6d0a5587

qmail.eclass: simplify is_prime()

The previous algorithm would scan for all primes for a given number, which
takes needlessly long.

Signed-off-by: Rolf Eike Beer <eike <AT> sf-mail.de>
Signed-off-by: Sam James <sam <AT> gentoo.org>

 eclass/qmail.eclass   | 51 ++++++++++++++++++--------------------------------
 eclass/tests/qmail.sh | 52 +++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 70 insertions(+), 33 deletions(-)

diff --git a/eclass/qmail.eclass b/eclass/qmail.eclass
index 8d05578dc3d..3cd8497363b 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

next             reply	other threads:[~2021-08-17  1:41 UTC|newest]

Thread overview: 44+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-08-17  1:41 Sam James [this message]
  -- strict thread matches above, loose matches on Subject: below --
2025-05-14  8:14 [gentoo-commits] repo/gentoo:master commit in: eclass/, eclass/tests/ Ulrich Müller
2025-05-06  8:46 Sam James
2025-05-01 11:36 Michał Górny
2024-12-15  9:47 Sam James
2024-05-14  8:20 Florian Schmaus
2024-02-10 10:47 Michał Górny
2024-02-10 10:47 Michał Górny
2023-10-09 10:54 Florian Schmaus
2023-09-14  5:30 Michał Górny
2023-06-07  7:00 Ulrich Müller
2023-05-23  4:36 Michał Górny
2023-03-21  5:43 Michał Górny
2023-03-17 22:04 David Seifert
2023-02-12 19:05 Michał Górny
2022-12-24 20:16 Michał Górny
2022-10-19 11:53 Michał Górny
2022-10-10 20:52 Michał Górny
2022-09-27 20:28 Michał Górny
2022-09-27 20:28 Michał Górny
2022-09-27 20:28 Michał Górny
2022-05-09 20:33 Michał Górny
2022-04-02 16:29 Michał Górny
2022-01-09  8:09 Michał Górny
2021-06-01 17:27 Sergei Trofimovich
2020-05-28 11:41 Michał Górny
2020-03-27 23:54 Sergei Trofimovich
2020-03-20 22:33 Sergei Trofimovich
2020-01-26 22:47 Sergei Trofimovich
2019-12-30 12:59 Michał Górny
2019-12-30 12:59 Michał Górny
2019-10-19 21:20 Sergei Trofimovich
2019-06-23  8:53 Sergei Trofimovich
2018-08-15  7:31 Michał Górny
2017-09-26 18:46 Ulrich Müller
2017-08-25 13:53 Michał Górny
2016-12-18 13:47 Michał Górny
2016-06-26 15:36 Michał Górny
2016-05-29  9:23 Amadeusz Piotr Żołnowski
2016-05-22 22:06 Amadeusz Piotr Żołnowski
2016-01-08  5:14 Michał Górny
2015-11-11 10:27 Michał Górny
2015-11-11 10:27 Michał Górny
2015-11-11 10:27 Michał Górny

find likely ancestor, descendant, or conflicting patches for this message:
( dfblob:8d05578dc3 dfblob:3cd8497363 dfblob:3520ed2a9d )
 OR (
bs:"[gentoo-commits] repo/gentoo:master commit in: eclass/, eclass/tests/" )
	(help)

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=1629164477.6d0a5587e8f7d51544824fb7eb806ba5c4dcb4e7.sam@gentoo \
    --to=sam@gentoo.org \
    --cc=gentoo-commits@lists.gentoo.org \
    --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