1 |
The previous algorithm would scan for all primes for a given number, which |
2 |
takes needlessly long. |
3 |
|
4 |
Signed-off-by: Rolf Eike Beer <eike@×××××××.de> |
5 |
--- |
6 |
eclass/qmail.eclass | 51 +++++++++++++++--------------------------- |
7 |
eclass/tests/qmail.sh | 52 +++++++++++++++++++++++++++++++++++++++++++ |
8 |
2 files changed, 70 insertions(+), 33 deletions(-) |
9 |
create mode 100755 eclass/tests/qmail.sh |
10 |
|
11 |
diff --git a/eclass/qmail.eclass b/eclass/qmail.eclass |
12 |
index 40130a502cb..9f644dd74c8 100644 |
13 |
--- a/eclass/qmail.eclass |
14 |
+++ b/eclass/qmail.eclass |
15 |
@@ -29,46 +29,31 @@ GENQMAIL_S="${WORKDIR}"/genqmail-${GENQMAIL_PV} |
16 |
QMAIL_SPP_F=qmail-spp-${QMAIL_SPP_PV}.tar.gz |
17 |
QMAIL_SPP_S="${WORKDIR}"/qmail-spp-${QMAIL_SPP_PV} |
18 |
|
19 |
-# @FUNCTION: primes |
20 |
-# @USAGE: <min> <max> |
21 |
+# @FUNCTION: is_prime |
22 |
+# @USAGE: <number> |
23 |
# @DESCRIPTION: |
24 |
-# Prints a list of primes between min and max inclusive |
25 |
-# Note: this functions gets very slow when used with large numbers. |
26 |
-primes() { |
27 |
- local min=${1} max=${2} |
28 |
- local result= primelist=2 i p |
29 |
+# Checks wether a number is a valid prime number for queue split |
30 |
+is_prime() { |
31 |
+ local number=${1} i |
32 |
+ |
33 |
+ if [[ ${number} -lt 7 ]]; then |
34 |
+ # too small |
35 |
+ return 1 |
36 |
+ fi |
37 |
|
38 |
- [[ ${min} -le 2 ]] && result="${result} 2" |
39 |
+ if [[ $[number % 2] == 0 ]]; then |
40 |
+ return 1 |
41 |
+ fi |
42 |
|
43 |
- for ((i = 3; i <= max; i += 2)) |
44 |
+ # let i run up to the square root of number |
45 |
+ for ((i = 3; i * i <= number; i += 2)) |
46 |
do |
47 |
- for p in ${primelist} |
48 |
- do |
49 |
- [[ $[i % p] == 0 || $[p * p] -gt ${i} ]] && \ |
50 |
- break |
51 |
- done |
52 |
- if [[ $[i % p] != 0 ]] |
53 |
- then |
54 |
- primelist="${primelist} ${i}" |
55 |
- [[ ${i} -ge ${min} ]] && \ |
56 |
- result="${result} ${i}" |
57 |
+ if [[ $[number % i ] == 0 ]]; then |
58 |
+ return 1 |
59 |
fi |
60 |
done |
61 |
|
62 |
- echo ${result} |
63 |
-} |
64 |
- |
65 |
-# @FUNCTION: is_prima |
66 |
-# @USAGE: <number> |
67 |
-# @DESCRIPTION: |
68 |
-# Checks wether a number is a prime number |
69 |
-is_prime() { |
70 |
- local number=${1} i |
71 |
- for i in $(primes ${number} ${number}) |
72 |
- do |
73 |
- [[ ${i} == ${number} ]] && return 0 |
74 |
- done |
75 |
- return 1 |
76 |
+ return 0 |
77 |
} |
78 |
|
79 |
dospp() { |
80 |
diff --git a/eclass/tests/qmail.sh b/eclass/tests/qmail.sh |
81 |
new file mode 100755 |
82 |
index 00000000000..3520ed2a9d5 |
83 |
--- /dev/null |
84 |
+++ b/eclass/tests/qmail.sh |
85 |
@@ -0,0 +1,52 @@ |
86 |
+#!/bin/bash |
87 |
+# Copyright 2020-2021 Gentoo Authors |
88 |
+# Distributed under the terms of the GNU General Public License v2 |
89 |
+ |
90 |
+EAPI=8 |
91 |
+source tests-common.sh |
92 |
+ |
93 |
+inherit qmail |
94 |
+ |
95 |
+# some numbers are blocked because they are to small even if prime |
96 |
+test_low_numbers() { |
97 |
+ tbegin "low numbers" |
98 |
+ |
99 |
+ for i in $(seq 0 6); do |
100 |
+ if is_prime ${i}; then |
101 |
+ return tend 1 "${i} badly accepted" |
102 |
+ fi |
103 |
+ done |
104 |
+ |
105 |
+ tend 0 |
106 |
+} |
107 |
+ |
108 |
+# test a given number for being prime |
109 |
+check_prime_number() { |
110 |
+ # use factor from coreutils to count the factors |
111 |
+ if [[ $(factor $1 | cut -d: -f2 | wc -w) == 1 ]]; then |
112 |
+ return $(is_prime $1) |
113 |
+ else |
114 |
+ return $(is_prime $1 && false || true) |
115 |
+ fi |
116 |
+} |
117 |
+ |
118 |
+test_primes() { |
119 |
+ tbegin "factorizations from ${1} to ${2}" |
120 |
+ |
121 |
+ for i in $(seq ${1:?} ${2:?}); do |
122 |
+ if ! check_prime_number $i; then |
123 |
+ tend 1 "${i} returned bad factorization" |
124 |
+ return 1 |
125 |
+ fi |
126 |
+ done |
127 |
+ |
128 |
+ tend 0 |
129 |
+} |
130 |
+ |
131 |
+test_low_numbers |
132 |
+test_primes 7 99 |
133 |
+for i in $(seq 100 100 1000); do |
134 |
+ test_primes $i $((i + 99)) |
135 |
+done |
136 |
+ |
137 |
+texit |
138 |
-- |
139 |
2.26.2 |