Mailing List Archive

[PATCH] 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@sf-mail.de>
---
eclass/qmail.eclass | 45 ++++++++++++---------------------------------
1 file changed, 12 insertions(+), 33 deletions(-)

diff --git a/eclass/qmail.eclass b/eclass/qmail.eclass
index f42f0491515..aaec205a6bd 100644
--- a/eclass/qmail.eclass
+++ b/eclass/qmail.eclass
@@ -20,46 +20,25 @@ 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>
-# @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
-
- [[ ${min} -le 2 ]] && result="${result} 2"
-
- for ((i = 3; i <= max; 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}"
- fi
- done
-
- echo ${result}
-}
-
-# @FUNCTION: is_prima
+# @FUNCTION: is_prime
# @USAGE: <number>
# @DESCRIPTION:
# Checks wether a number is a prime number
is_prime() {
local number=${1} i
- for i in $(primes ${number} ${number})
+
+ if [[ $[number % 2] == 0 ]]; then
+ return 1
+ fi
+
+ for ((i = 3; i * i <= number; i += 2))
do
- [[ ${i} == ${number} ]] && return 0
+ if [[ $[number % i ] == 0 ]]; then
+ return 1
+ fi
done
- return 1
+
+ return 0
}

dospp() {
--
2.26.2
Re: [PATCH] qmail.eclass: simplify is_prime() [ In reply to ]
Rolf Eike Beer wrote:
> The previous algorithm would scan for all primes for a given number,
> which takes needlessly long.

Please also mention how this caused a problem for you in the commit
message, to help us understand why you're proposing to change this.


> +++ b/eclass/qmail.eclass
> -# @FUNCTION: is_prima
> +# @FUNCTION: is_prime
> # @USAGE: <number>
> # @DESCRIPTION:
> # Checks wether a number is a prime number

Maybe name the algorithm? Looks like an optimization of the sieve of
Eratosthenes?


> is_prime() {
> local number=${1} i
> - for i in $(primes ${number} ${number})
> +
> + if [[ $[number % 2] == 0 ]]; then
> + return 1
> + fi

While 2 itself is prime the above returns 1 for any even number.


> + for ((i = 3; i * i <= number; i += 2))
> do
> - [[ ${i} == ${number} ]] && return 0
> + if [[ $[number % i ] == 0 ]]; then

An inconsistent space after "% i" here. I don't know what style is correct.


//Peter
Re: [PATCH] qmail.eclass: simplify is_prime() [ In reply to ]
Hi,

On Thu, Jun 17, 2021 at 05:42:12PM +0000, Peter Stuge wrote:
> Rolf Eike Beer wrote:
> > The previous algorithm would scan for all primes for a given number,
> > which takes needlessly long.
>
> Please also mention how this caused a problem for you in the commit
> message, to help us understand why you're proposing to change this.
>
>
> > +++ b/eclass/qmail.eclass
> > -# @FUNCTION: is_prima
> > +# @FUNCTION: is_prime
> > # @USAGE: <number>
> > # @DESCRIPTION:
> > # Checks wether a number is a prime number
>
> Maybe name the algorithm? Looks like an optimization of the sieve of
> Eratosthenes?
>
>
> > is_prime() {
> > local number=${1} i
> > - for i in $(primes ${number} ${number})
> > +
> > + if [[ $[number % 2] == 0 ]]; then
> > + return 1
> > + fi
>
> While 2 itself is prime the above returns 1 for any even number.

There's actually a much simpler solution to this:

$ is_prime() { test $(factor $1 | cut -d: -f2 | wc -w) == 1; }
$ for n in $(seq 0 10); do is_prime $n && echo $n is prime; done
2 is prime
3 is prime
5 is prime
7 is prime
$ time factor 20187319083467888113
20187319083467888113: 20187319083467888113
0.00

Cheers,
-Guilherme
Re: [PATCH] qmail.eclass: simplify is_prime() [ In reply to ]
>>>>> On Thu, 17 Jun 2021, Guilherme Amadio wrote:

> There's actually a much simpler solution to this:

> $ is_prime() { test $(factor $1 | cut -d: -f2 | wc -w) == 1; }
> $ for n in $(seq 0 10); do is_prime $n && echo $n is prime; done
> 2 is prime
> 3 is prime
> 5 is prime
> 7 is prime
> $ time factor 20187319083467888113
> 20187319083467888113: 20187319083467888113
> 0.00

This depends on the actual domain of numbers. If the primes involved
have 20 digits as in your example, then factor should be used of course.

I suspect though that we're talking about small numbers (below 100?)
here, in which case a solution in pure bash would be preferable.

Ulrich
Re: [PATCH] qmail.eclass: simplify is_prime() [ In reply to ]
>
> This depends on the actual domain of numbers. If the primes involved
> have 20 digits as in your example, then factor should be used of course.
>
> I suspect though that we're talking about small numbers (below 100?)
> here, in which case a solution in pure bash would be preferable.
>

If so, we could just list them all.
Re: [PATCH] qmail.eclass: simplify is_prime() [ In reply to ]
Am Freitag, 18. Juni 2021, 21:10:27 CEST schrieb Michael Orlitzky:
> > This depends on the actual domain of numbers. If the primes involved
> > have 20 digits as in your example, then factor should be used of course.
> >
> > I suspect though that we're talking about small numbers (below 100?)
> > here, in which case a solution in pure bash would be preferable.
>
> If so, we could just list them all.

The primes are usually small, the default is 23, and I have never seen anyone
_lowering_ that number. The whole point is: the algorithm does much more than
it should, which makes it needlessly verbose. The simpler the solution the
better, preferably without restricting the actual number.

Eike