From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from lists.gentoo.org (pigeon.gentoo.org [208.92.234.80]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by finch.gentoo.org (Postfix) with ESMTPS id A0020158F56 for ; Tue, 17 Aug 2021 01:41:33 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id 89206E0830; Tue, 17 Aug 2021 01:41:32 +0000 (UTC) Received: from smtp.gentoo.org (woodpecker.gentoo.org [IPv6:2001:470:ea4a:1:5054:ff:fec7:86e4]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by pigeon.gentoo.org (Postfix) with ESMTPS id 5829DE0827 for ; Tue, 17 Aug 2021 01:41:32 +0000 (UTC) Received: from oystercatcher.gentoo.org (oystercatcher.gentoo.org [148.251.78.52]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.gentoo.org (Postfix) with ESMTPS id 6C46533E830 for ; Tue, 17 Aug 2021 01:41:31 +0000 (UTC) Received: from localhost.localdomain (localhost [IPv6:::1]) by oystercatcher.gentoo.org (Postfix) with ESMTP id D26318B3 for ; Tue, 17 Aug 2021 01:41:29 +0000 (UTC) From: "Sam James" To: gentoo-commits@lists.gentoo.org Content-Transfer-Encoding: 8bit Content-type: text/plain; charset=UTF-8 Reply-To: gentoo-dev@lists.gentoo.org, "Sam James" Message-ID: <1629164477.6d0a5587e8f7d51544824fb7eb806ba5c4dcb4e7.sam@gentoo> Subject: [gentoo-commits] repo/gentoo:master commit in: eclass/, eclass/tests/ X-VCS-Repository: repo/gentoo X-VCS-Files: eclass/qmail.eclass eclass/tests/qmail.sh X-VCS-Directories: eclass/ eclass/tests/ X-VCS-Committer: sam X-VCS-Committer-Name: Sam James X-VCS-Revision: 6d0a5587e8f7d51544824fb7eb806ba5c4dcb4e7 X-VCS-Branch: master Date: Tue, 17 Aug 2021 01:41:29 +0000 (UTC) Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail X-BeenThere: gentoo-commits@lists.gentoo.org X-Auto-Response-Suppress: DR, RN, NRN, OOF, AutoReply X-Archives-Salt: de365392-54f6-4408-a016-e1180f349b01 X-Archives-Hash: c9c45d4101fb6321c546f7c94cb573b2 commit: 6d0a5587e8f7d51544824fb7eb806ba5c4dcb4e7 Author: Rolf Eike Beer sf-mail de> AuthorDate: Thu Jun 17 14:39:07 2021 +0000 Commit: Sam James gentoo 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 sf-mail.de> Signed-off-by: Sam James 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: +# @FUNCTION: is_prime +# @USAGE: # @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: -# @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