素数の問題です。 11から1231までに存在する素数の個数を求めるやり

質問

素数の問題です。 11から1231までに存在する素数の個数を求めるやりかたと答えを教えてください。

回答No.2

NNori · ベストアンサー

エラトステネスのふるい、で全部列挙しちゃうのがいいと思います。
１２３１のルートは、35.08なので、２から３１までの素数の倍数をつぶせばOK

お礼

ありがとうございます。
倍数のつぶし方ですが、このようにたくさんの素数が存在するときベン図のようには考えられないですよね？
どう考えれば簡単になるでしょうか。

回答No.3

laputart

EXCELを使ってマクロを作ると、こんな感じです。
セルB4に素数の数がカウントされます。
B5～は素数を順に表示します。

Sub Macro1()

'N0 = 最小の数　（この場合１１をセルB1に入力
'N1 = 最大の数　（セルB2に入力
'CT = 素数の数カウント
'N = 調べている数字　(N0 から　N1まで）
'I = 2～　√Nまで順に検査　割り切れれば、OK=1 にする。そうでない場合は素数
' 割り切れる判定は　N/I = INT(N/I) になるかどうか
'L = 素数を表示する行番号

Dim N0, N1, CT, OK, L As Integer

CT = 0
L = 5
N0 = Range("B1").Value
N1 = Range("B2").Value

OK = 0
If Not IsNumeric(N0) Then OK = 1
If Not IsNumeric(N1) Then OK = 1

If OK = 1 Then
MsgBox ("最小数、最大数を入力してください")
End
End If

For N = N0 To N1
OK = 0
i = 2
Do Until i > Int(Sqr(N))
If N / i = Int(N / i) Then OK = 1: Exit Do
i = i + 1
Loop
If OK = 0 Then
CT = CT + 1
Range("B4").Value = CT
Z = "B" & CStr(L)
Range(Z).Value = N
L = L + 1
End If
Next N
End Sub

お礼

ありがとうございます。

回答No.1

alice_44

#include <stdio.h>
#include <math.h>

#define Nfrom 11
#define Nto 1231
static char sieve[N+1];

main(){
　int count = 0;
　int root = (int)sqrt(Nto);

　for(i = 2; i <= root; i++) if(sieve[i] == 0)
　　for(k = i; (k += i) <= Nto; ) seive[k] = 1;

　for(i = Nfrom; i <= Nto; i++)
　　if(sieve[i] == 0) ++count;

　printf("%d\n", count);
}

ホントにコンパイルして実行させたら、カテ違い。
配列 sieve[ ] を紙に書いて、パソコンになったつもりで
手計算でコレをやってみよう。

お礼

ありがとうございます。