| 1 |
Hi, |
| 2 |
|
| 3 |
On Thu, Jun 17, 2021 at 05:42:12PM +0000, Peter Stuge wrote: |
| 4 |
> Rolf Eike Beer wrote: |
| 5 |
> > The previous algorithm would scan for all primes for a given number, |
| 6 |
> > which takes needlessly long. |
| 7 |
> |
| 8 |
> Please also mention how this caused a problem for you in the commit |
| 9 |
> message, to help us understand why you're proposing to change this. |
| 10 |
> |
| 11 |
> |
| 12 |
> > +++ b/eclass/qmail.eclass |
| 13 |
> > -# @FUNCTION: is_prima |
| 14 |
> > +# @FUNCTION: is_prime |
| 15 |
> > # @USAGE: <number> |
| 16 |
> > # @DESCRIPTION: |
| 17 |
> > # Checks wether a number is a prime number |
| 18 |
> |
| 19 |
> Maybe name the algorithm? Looks like an optimization of the sieve of |
| 20 |
> Eratosthenes? |
| 21 |
> |
| 22 |
> |
| 23 |
> > is_prime() { |
| 24 |
> > local number=${1} i |
| 25 |
> > - for i in $(primes ${number} ${number}) |
| 26 |
> > + |
| 27 |
> > + if [[ $[number % 2] == 0 ]]; then |
| 28 |
> > + return 1 |
| 29 |
> > + fi |
| 30 |
> |
| 31 |
> While 2 itself is prime the above returns 1 for any even number. |
| 32 |
|
| 33 |
There's actually a much simpler solution to this: |
| 34 |
|
| 35 |
$ is_prime() { test $(factor $1 | cut -d: -f2 | wc -w) == 1; } |
| 36 |
$ for n in $(seq 0 10); do is_prime $n && echo $n is prime; done |
| 37 |
2 is prime |
| 38 |
3 is prime |
| 39 |
5 is prime |
| 40 |
7 is prime |
| 41 |
$ time factor 20187319083467888113 |
| 42 |
20187319083467888113: 20187319083467888113 |
| 43 |
0.00 |
| 44 |
|
| 45 |
Cheers, |
| 46 |
-Guilherme |
Archives