The previous algorithm would scan for all primes for a given number, which takes needlessly long.
Signed-off-by: Rolf Eike Beer <[email protected]> --- 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
signature.asc
Description: This is a digitally signed message part.
