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