Pythonアルゴリズム007|小数(テストステロン体)**定期復習が必要
7.少数(メスステロイド)
自然数Nを入力すると、1からNまでの少数の数を出力するプログラムを作成します.
20を入力すると、1~20の小数は2、3、5、7、11、13、17、19の計8個になります.
制限時間は1秒です.
■説明の入力
1行目は自然数N(2<=N<=20000)を与える.
■出力説明
最初の行に小数を出力します.
■入力例1
20
■出力例1
8
『私の答え』
n=int(input())
res=0
for i in range(1,n+1) :
cnt=0
for x in range(2,i) :
if i%x==0 :
cnt+=1
if cnt==0 :
res+=1
print(res-1)
<解答>
素数を求める時、ラステナイトの方法を使うのは最も速いです
エラスト・テネスとは?
小数を手に入れたときにリストを並べます.
2から0(2,3,5)カウントダウン.
彼の排水を全部消しなさい(2の倍数、3の倍数、5の倍数...)(ふるいのように)
n=int(input())
cnt=0
ch=[0]*(n+1)
for i in range(2,n+1) :
if ch[i]==0:
cnt+=1
for j in range(i,n+1, i) :
ch[j]=1
print(cnt)
2,3,5..同じ子を数えながら、1を排水槽に入れます.後からa[i]=0まで数えた子は、小数を落とすことになります.
『反省点』
『学んだこと』
小数が1より大きい数
すべてが1つの数字の倍数に近づく場合はrange(start、end、start)を選択し、startの倍数だけを選択します.
エラトネスのふるいを用いると,少数自身を除く少数の倍数をより速く得ることができる(3が少数であれば,その倍数は3,6,9...)3を約数とする数字なので、当然3(=少数ではない)にも分けられます.
最終的に、実際の実装方法は2から始まり、要求された数値リストを0に初期化し、リストの値が0の数値(=小数)の場合、countに1を加算する繰り返し文を作成することである.次に、リストの値を1に設定する数少ない倍数の重複文を作成します.
これにより,外部繰返し文が次の数字に到達した場合,if文のリストの値が0でなければcountも上昇せず,中の繰返し文も実行されないため,少数の数を速やかに求めることができる.
if ch[i]==0:
cnt+=1
for j in range(i,n+1, i) :
ch[j]=1
Reference
この問題について(Pythonアルゴリズム007|小数(テストステロン体)**定期復習が必要), 我々は、より多くの情報をここで見つけました https://velog.io/@myway00/파이썬-알고리즘-007-소수에라토스테네스-체テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol