[プログラマ]小数点を検索


こんにちは。


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で検索してください)

説明:

  • サイズnのリストを1で埋めます.
  • 2からn-1の数字iが小数であるか否かを判別する.
  • iの2倍以上は小数ではないので、0はその数字のリストインデックスを表します.
    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)		# 모든 값을 더해서 개수를 구함
    最初は良い値が欲しかったのですが、失敗したら慌ててしまうかもしれません.
    小数を求める方法はよく実現されていますが、この問題で要求されるアルゴリズムを使用していないためです.
    「エラトスのふるい」を知っていれば、大丈夫ですが、
    もしあなたが知らないなら、あなたは問題を解くのにきっと苦労しているに違いありません......私も昔は...!!
    今日の問題はこれで終わります.
    皆さんはコロナ市の国なので家にいるしかなく、旅行もイベントもできず、疲れていますが頑張りましょう.😎👍
    では.

    さようなら~~