☰

只有素数吗？

tag-icon • tag-icon bash math algorithms
只有素数吗？

试图完成欧拉计划 #5。我的代码在逻辑上应该可以工作，并且它通过了 ShellCheck，但由于某种原因没有给出输出。代码如下。谢谢，抱歉，如果这应该在不同的堆栈交换站点中

#!/bin/bash
 i=1
 while [[ $((i % 2)) -eq 0 && $((i % 3)) -eq 0 && $((i % 5)) -eq 0 && $((i % 7)) -eq 0 && $((i % 11)) -eq 0 && $((i % 13)) -eq 0 && $((i % 17)) -eq 0 && $((i  % 19)) -eq 0 ]]
 do
     i=$((i+1))
 done
 echo $i

答案1

是的，你应该进行测试[[ $((i % 2)) -eq 0 && $((i % 3)) -eq 0 … … ]]。它将测试一个数字是否可以$i被列表中的所有数字整除， 同时。但如果数字与测试相符，你会做什么呢？打印它是因为您找到了号码？

不，你正在增加它。你需要的是扭转这个动作；换句话说：

$i如果测试失败则增加。

要么做：

while ! [[ … . … ]]; do

或者：

until [[ … . … ]]; do

这样做将花费大量时间才能找到 9699690（您用代码寻找的数字，这也不是正确的答案）。

正确的查找方法就在前面；继续阅读。

只有素数吗？

但是，为什么你不包括，例如 4 或 6 或 9 等......

因为它们不是素数？让我用一个例子来阐明这个想法。
数字 9699690 可被测试中的所有素数 (2 3 5 7 9 11 13 17 19) 整除，但不能被 4 整除。

你写的代码失败了。通过蛮力找到答案需要很长时间（尝试每一个整数，直到找到正确的整数，特别是在 shell 中，这是最慢的语言之一）。

液晶模组

但如果我们这样描述问题可能会更容易：

找到列表 {1..20} 的 LCM。

那就是L东方C奥蒙中号几个数字的倍数。最小公倍数是：（ LCM(a,b) = (a×b) / gcd(a,b)数学方程）。

GCD

其中 gcd 是G重新测试C奥蒙Divisor。

欧几里得（大约2300年前）描述了第一个。  欧几里得算法是计算两个数字的最大公约数 (GCD) 的有效方法。

现代 shell 中作为函数的实现非常简单：

gcd() {   # Calculate $1 % $2 until $2 becomes zero.
          until [ "$2" -eq 0 ]; do set -- "$2" "$(($1%$2))"; done
          echo "$1"
      }

然后 lcm 代码也很简单：

lcm() {   echo "$(( $1 / $(gcd "$1" "$2") * $2 ))";   }

需要的是循环所有给定的参数，直到只剩下一个：

while  [ $# -gt 1 ]
do
       t="$(lcm "$1" "$2")"
       shift 2
       set -- "$t" "$@"
done
echo "$1"

使用您使用的号码调用整个程序给出了我上面使用的号码：

$ ./script 2 3 5 7 11 13 17 19
9699690

您可以将该脚本称为：

$ ./script {2..20}

才能得到最终的答案。

答案2

必须用bashas tagged 来解决吗？

如果是这样，让我们​​使用这里字符串机制：

$ bc <<< '9*8*7*5'
2520
$ bc <<< '19*18*17*13*11*8*7*5'
232792560

要点是将不可被先前数字整除的最大数字相乘。例如，在第一种情况下，我们有9*8*7*...（并且没有 6，因为 9 可以被 3 整除，8 可以被 2 整除，所以 8*9 肯定可以被 6 整除）*5...。显然4,3和2也能被8,9和8整除。

经过一番思考，我意识到对于任何长度的序列来说，更通用的方法可能是将所有素数相乘，如果不是素数，则仅乘以剩余部分，所以

2*3*2*5*1*7*2*3*1*11*1*13*1*1*2*17*1*19

我们用 2 代替数字 4，因为第二个 2 已经在那里，在数字 8 和 16 的情况下使用了类似的技巧。数字 6 被 2*3 覆盖，所以我们用 1，类似地对于数字 10,12,14,15 ,18.最后将 9 替换为 3。显然，所有这些都可以通过19*18*17*13*11*8*7*5前面提到的方法进行简化。

相关内容