블룸 정수-C++-php.cn

블룸 정수

王林

풀어 주다： 2023-08-29 18:41:06

앞으로

860명이 탐색했습니다.

블룸 정수

문제 설명은 Blum 번호인 경우 사용자 입력으로 입력될 특정 번호를 확인하는 것으로 구성됩니다.

A Blum 정수 는 소인수 a와 b가 4t+3 형식인 준소수입니다. 여기서 t는 양의 정수입니다. 세미소수는 정확히 두 개의 소수의 곱인 수, 또는 정확히 두 개의 소인수를 갖는 자연수입니다. 세미프라임의 경우 인수가 동일할 수 있습니다.

임의의 숫자 N이 블룸 정수인 경우 1 대신 N=a*b와 같이 두 개의 인수만 있어야 하며 숫자 자체와 두 인수인 a와 b는 4t+3 형식의 서로 다른 소수여야 합니다( 임의의 양의 정수 t에 대해).

처음 몇 개의 blum 정수는 21, 33, 57, 69, 77, 93, 129, 133, 141...

두 개의 비소인수(4t+3(예: 홀수) 형식)의 곱은 항상 20보다 큰 홀수가 되기 때문에 자연수도 퍼지 정수가 될 수 없습니다.

이 문제에서는 숫자 N이 주어지며 그 숫자가 블룸 정수인지 확인해야 합니다.

예

으아악

지침: 입력에 제공된 숫자는 57입니다. 숫자 57은 19와 3의 곱(즉, 19*3)으로 표현될 수 있습니다. 두 요소 모두 4t+3 형태의 서로 다른 소수이기 때문입니다.

19=4*4+3, 이 예에서 t 값은 4입니다.

3=4*0+3, t의 값은 0입니다.

따라서 숫자 57은 블룸 정수입니다.

으아악

설명: 주어진 숫자는 49이며 7*7로 표현할 수 있습니다. 7은 소수이기 때문에 숫자의 경우 두 개의 서로 다른 소수의 곱이어야 합니다. 따라서 49는 퍼지 정수가 아닙니다.

으아악

설명: 숫자 35는 7과 5의 곱으로 표현될 수 있습니다(예: 7*5). 두 숫자는 서로 다른 소수입니다. 7은 4t+3 형식이지만 5는 t의 정수 값에 대해 4t+3으로 표시될 수 없습니다. 따라서 35는 모호한 정수가 아닙니다.

숫자가 블룸 정수인지 확인하는 알고리즘을 이해해 봅시다.

알고리즘

숫자가 블룸 정수인지 확인하려면 숫자 앞의 모든 소수를 찾은 다음 4t+3 형식의 서로 다른 두 소수의 곱이 주어진 숫자를 형성할 수 있는지 확인하면 됩니다.

우리는 에라토스테네스의 체 개념을 사용하여 주어진 숫자 N까지의 모든 소수를 찾습니다. 에라토스테네스의 체는 주어진 숫자 N 앞에 오는 소수의 수를 찾는 가장 효율적인 방법입니다.

이 방법에서는 N+1 크기의 부울 배열을 생성합니다. 여기서 N은 주어진 숫자입니다. 숫자가 이 숫자와 인덱스 값이 같은 소수이면 true를 저장하고, 그렇지 않으면 배열에 false를 저장합니다.
N까지 소수가 아닌 숫자에 해당하는 인덱스 값 false를 업데이트하려면 for 루프에서 i=2에서 i
i에 해당하는 arr[i]의 값이 true이면 중첩 루프에서 p=i*i부터 p

에라토스테네스의 체를 이용하면 1부터 N까지의 소수를 모두 구할 수 있습니다. 이제 배열의 for 루프를 반복하면서 주어진 숫자 N의 인수이고 4t+3 형식의 소수가 있는지 확인하고 소수를 N으로 나눈 몫도 다음과 같습니다. 4t+3 형식 다른 소수. 위의 조건이 모두 충족되면 주어진 숫자 N은 blum 정수가 되고, 그렇지 않으면 그렇지 않습니다.

우리는 문제를 효율적으로 해결하기 위해 접근 방식에 이 알고리즘을 사용할 것입니다.