有害数

#数値が正の整数であり、そのバイナリ展開で設定された桁数が素数である場合、その数値は有害であるとみなされます。 3 = (11)₂ であるため、最初の有害な数は 3 です。 3 の 2 進数表現には、素数である 2 の桁数が設定されていることがわかります。

有害な数字のトップ 10 は、3、5、6、7、9、10、11、12、13、14 です。興味深いことに、2 の累乗は常に 1 ビットのみが設定されているため、有害な数値になることはありません。 1は素数ではありません。一方、2ⁿ1 (n は任意の自然数) として表現できるすべての数値は、2 つのセットビットを持ち、2 が素数であることがわかっているため、常に不正な数値になります。番号。

これらの有害な数値の特性を念頭に置き、次の記事では、数値が有害かどうかを確認する方法について説明します。

＃＃＃問題文＃＃＃

この質問は、指定された数値 n が有害な数値であるかどうか、つまり、バイナリ展開で素数のセット ビットを持つ正の数値であるかどうかを確認することを目的としています。

＃＃＃例＃＃＃ リーリー リーリー

説明

の翻訳は次のとおりです:

説明

37 = 100101 のバイナリ表現。

桁数 = 3

を設定します。

3 は素数なので、37 は悪い数です。

リーリー リーリー

説明

の翻訳は次のとおりです:

説明

22 = 10110 のバイナリ表現。

桁数 = 3 を設定します。

3 は素数なので、22 は凶数です。

リーリー リーリー

説明

の翻訳は次のとおりです:

説明

71 のバイナリ表現は 1000111 です。

桁数 = 4 を設定します。

4 は素数ではないので、71 も有害な数ではありません。

リーリー リーリー

説明

の翻訳は次のとおりです:

説明

64 のバイナリ表現は 1000000 です。

桁数 = 1 を設定します。

64 = 2

6

、つまり 2 の累乗であるため、セット ビットが 1 つあります。 1 は素数ではないので、64 は凶数ではありません。

＃＃＃解決＃＃＃

数値が悪意があるかどうかを判断するには、設定された桁数が素数であるかどうかを知る必要があります。ここでの主なタスクは、この数値の 2 進展開で設定された桁数を計算することです。次の方法を使用して、設定された桁数を計算し、結果が素数であるかどうかを判断できます。 この方法には次の手順が含まれます -

ループ演算子と右シフト演算子を使用して、数値のすべてのビットを反復処理します。

ビット値が 1 の場合、設定されたビットのカウントが 1 増加します。
カウントの最終値が素数かどうかを確認します。
答えを表示します。

• ＃＃＃アルゴリズム＃＃＃
関数 is_prime()
If (n

エラーを返す

for (i から √a)
If (a%i==0)
• エラーを返す

trueを返す

関数 count_set_bits()

• 初期化カウンタ = 0

(n > 0)の場合

• If ((n & 1) > 0)

• カウンター = カウンター 1

• n = n >> 1

返品カウンター
関数 is_pernious()

• カウンタを初期化します

カウンター = count_set_bits(n)

• if (is_prime(counter) == true)

• trueを返す

• ＃＃＃＃＃＃他の＃＃＃＃＃＃

エラーを返す
関数 main()

• nを初期化します

if (is_pernious())

cout

• ＃＃＃＃＃＃他の＃＃＃＃＃＃

cout

印刷出力

例: C プログラム

• プログラムは、関数

is_pernicious()
を使用して、数値が有害かどうかを判断します。関数

count_set_bits()

の各反復の終わりに値を n だけ右にシフトすることにより、ループの各反復の最下位ビットを分析します。次に関数
is_prime()
を呼び出して、設定した桁数が素数かどうかを収集します。
• リーリー ＃＃＃出力＃＃＃ リーリー

  時空分析

時間計算量: O(log(n) sqrt(count))

。関数

count_set_bits()

では、数値をビットごとに分析しながら、ループが log(n) 回実行されます。関数 is_prime() は、count が素数かどうかを確認するのに O(sqrt(count)) 時間がかかります。どちらの関数も実行中に 1 回呼び出されます。

空間の複雑さ: O(1)

。実装では補助空間が使用されないためです。入力数値のサイズに関係なく、アルゴリズムは常に一定量のスペースを使用します。

＃＃＃結論は＃＃＃

有害な数値は興​​味深い数学的概念であり、上記の方法を使用して簡単かつ効果的に識別できます。この記事では、使用するアルゴリズム、C プログラム ソリューション、および時間と空間の複雑さの分析についても説明します。

以上が有害数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。