[プログラマ]小数点を検索
1903 ワード
こんにちは。
MINDOLです
この問題は名前だけでよく知っている少数の検索問題です.
知らないの?可能性もある.今から慣れればいい
素数は英語で「primenumber」と呼ばれています.英語で書くとかっこいいと思います
初期の根本的な基礎数字と解釈できますか?私もよくわかりません.
とりあえず今日は基本数字を探しましょうか?
小数点を検索
質問リンク
1からnまでの小数を検索します.
実は素数を求める方法は簡単です.
これは少数が1と自分に分かれていることを意味しているからです.
小数の数字がxであるか否かを判別するには、
2からx-1まで数字のうち1つが分かれていない場合は少数です.
したがって小数であるかどうかを知りたければ、複文2からx-1まで数字でxを除くことができます.
でも、そんなに簡単な問題はありませんよね?
これは、値を検索する問題だけではありません.
これは小数を求める最良の方法を探す問題である.
通常の繰り返し文を使用すると、1からnまでの繰り返し文には2からn-1までの繰り返し文が含まれ、時間的複雑度はO(n)である.²).
つまり、ネストされた重複文を直接使用すると、時間の制限によって失敗します.
従って、小数を求める場合には、2から平方根nに時間を短縮することができる.
しかし,この問題は1つの数字を判別するのではなく,10,000個に達する数字を判別するため,特殊なアルゴリズムを用いる必要がある.
名前
「エラトステネスのふるい」
.
(詳細については、Googleで検索してください)
説明:
ex)6は3の2倍で小数ではなく
メモリが多く使われていますが、
どのくらいの数の判別では,速度は確かに速い.
ではPythonコードを見てみましょう~~
def solution(n):
net = [1] * n # 1로 채워진 크기 n의 리스트
net[0] = 0 # 1을 소수가 아니다.
for i in range(2, n): # 따라서 2부터 n-1까지 비교
for j in range(2, n): # i의 2이상 배수는 소수가 아님
if i * j > n: # n-1까지 범위를 벗어나면 멈춤
break
net[i*j-1] = 0 # 소수가 아니므로 0 대입
return sum(net) # 모든 값을 더해서 개수를 구함
最初は良い値が欲しかったのですが、失敗したら慌ててしまうかもしれません.小数を求める方法はよく実現されていますが、この問題で要求されるアルゴリズムを使用していないためです.
「エラトスのふるい」を知っていれば、大丈夫ですが、
もしあなたが知らないなら、あなたは問題を解くのにきっと苦労しているに違いありません......私も昔は...!!
今日の問題はこれで終わります.
皆さんはコロナ市の国なので家にいるしかなく、旅行もイベントもできず、疲れていますが頑張りましょう.😎👍
では.
さようなら~~
Reference
この問題について([プログラマ]小数点を検索), 我々は、より多くの情報をここで見つけました
https://velog.io/@minskim2/프로그래머스-소수-찾기
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
Reference
この問題について([プログラマ]小数点を検索), 我々は、より多くの情報をここで見つけました https://velog.io/@minskim2/프로그래머스-소수-찾기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol