☰

소수만?

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로 나눌 수는 없습니다.

작성한 코드가 실패했습니다. 무차별 대입으로 답을 찾는 데는 오랜 시간이 걸립니다(특히 가장 느린 언어 중 하나인 셸에서 올바른 것을 찾을 때까지 모든 정수를 시도하십시오).

LCD 모듈

하지만 문제를 다음과 같이 설명하면 더 쉬울 수 있습니다.

목록 {1..20}에 대한 LCM을 찾습니다.

그건엘동쪽씨아몬중간 사이즈여러 숫자의 배수. 최소 공배수는 다음과 같습니다( LCM(a,b) = (a×b) / gcd(a,b)수학적 방정식).

GCD

gcd는 어디에 있나요?G재시험씨아몬디아이 바이저.

유클리드(약 2300년 전)가 첫 번째를 기술했습니다.  유클리드 알고리즘두 숫자의 최대 공약수(GCD)를 계산하는 효율적인 방법입니다.

최신 쉘에서 함수로 구현하는 것은 매우 간단합니다.

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

bash문제를 해결하려면 태그 지정을 사용해야 합니까 ?

그렇다면 활용해보자여기 문자열기구:

$ 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으로 덮여 있으므로 숫자 10, 12, 14, 15, 18에도 마찬가지로 1을 사용합니다. 마지막으로 9를 3으로 바꿉니다. 분명히 이 모든 것은 19*18*17*13*11*8*7*5앞서 언급한 방법으로 단순화될 수 있습니다.

관련 정보