概要
ざっくりと概要を言うと、素数を求める関数を3つ実装してみて～って問題です。
基本的には穴埋めで、最後に実際に値を入れた際にある部分が何回実行されるか答える問題があります。
今回はそんな複雑でないのでpythonで解いてます。
今回解いた問題 問3
1つ目のアルゴリズム
シンプルに全探索
d = 2
primes = []
isPrime = True
N=20
cnt = 0
# 全探索で素数を求める
while(d <= N):
isPrime = True
t = 2
while(t < d):
# d未満のtについて割り切れるか全探索する
if d % t == 0:
# 割り切れる場合は素数ではないのでfalseに
isPrime = False
t += 1 # (L1)
cnt += 1
# true(素数)の場合は結果に素数を格納する
if isPrime:
primes.append(d)
d += 1
# 素数の結果を表示
print(primes)
# L1の実行回数を表示(最終問題用)
print(cnt)
ここでは特に穴埋め問題はありません。
実行回数を数える(L1)
最終問題にN=20の時に(L1)の部分が何回実行されるか答える問題があります。
とりあえず、cnt変数用意してプログラムに数えてもらったんで、結果を素数とともに表示します。
[2, 3, 5, 7, 11, 13, 17, 19]
171
これの計算方法は、初期値d=2の時はwhile(tがd未満)の条件がfalseのため、実行回数は0回です。
次に、d=3の時は実行回数は1回です。
このようにdが1増えるごとに実行回数も1回ずつ増えていきd=20の時は18回実行されます。
よって、合計=0+1+2+3+4+....+18 = 18*19/2=171回が答えとなります。
2つ目のアルゴリズム
2つ目はdが素数である場合には、d以上のdをx倍した数については素数ではないとマークする方法です。
例えば、dが3の時は12,15,18とかは素数ではないとマークします。
d = 2
c = 2
primes = []
isPrime = []
isPrime.append(False)
N=20
cnt = 0
while(c <= N):
isPrime.append(True)
c += 1
while(d <= N):
if isPrime[d-1] == True: # (イ)
primes.append(d)
t = d*d
while(t <= N):
# 素数ではないのでfalseに変更
isPrime[t-1] = False
print(t)
t += d # (ウ)
cnt += 1
d += 1
print(primes)
print(cnt)
今回、実装の関係上配列について[d-1]など-1しているのですが、試験問題は配列の要素番号は1から始まるので答えと実装が少し異なります。
このアルゴリズムには穴埋め問題が2つあります。
穴埋め問題、(イ)について
(イ)については問題文の中にほぼ答えがかいてあります。
この処理はdが"素数である"とマークされている場合、行いますのでそれをそのまま書きます。
dが素数であるか、素数ではないかの情報はisPrime配列に格納しています。また、trueの時は素数のため答えは次のようになります。
(イ): isPrime[d]がtrueと等しい
穴埋め問題、(ウ)について
これは実際に値を代入してみたらわかりやすいと思います。
例えば、d=2の時はt=2*2=4が代入されます。
そのあとは、tがN以下の条件の時、(ウ)の処理を行いfalseである情報をisPrime配列に格納します。
ここで(ウ)の処理を考えるのですが、tの値が以下の時にfalseを格納したいはずです。
4
6
8
10
12
14
16
18
20
d=2の時は、2ずつ増やしていっていけばそれは全て素数ではないです。
そのため、(ウ)の答えは以下のようになります。
t+d
答えだけ見るとすごいシンプル
実行回数を数える(L2)
このアルゴリズムも同様に(L2)の部分の実行回数を数えます。
正直、これは愚直に1から数える方が速いと思います。
ひとまず、今回も実行回数と素数の結果、tの値を下にのせます。
4
6
8
10
12
14
16
18
20
9
12
15
18
[2, 3, 5, 7, 11, 13, 17, 19]
実行回数
13
これを見ればもう答えは13回で終わりです。
流石にそれだと雑すぎるので、まずd=2の場合を考えます。
d=2の場合
まず、tにはt=d*d=4が入ります。
そのあとは、tに2ずつ足していくので合計で9回(4,6,8,10,12,14,16,18,20)実行されます。
d=3の場合
こちらも同様の考えで、4回(9,12,15,18)実行されます。
d=4の場合
一瞬、d=4でt=4*4=16になりこちらも実行回数に入るのではと思っちゃうんですけど、そもそもd=4はすでに素数ではないとマークされてます。
そのため、(L2)の実行回数にはカウントされません。
d=5以降の場合
まず、d=5のため、tは25(5*5)になります。25はN(20)より大きいので(L2)の実行回数には入りません。
d=6以降も同様にカウントされません。
これで、これまでの実行回数を合計して9+4=13回が答えとなります。
3つ目のアルゴリズム
今回は4以上の偶数は絶対に素数ではないため奇数だけを配慮したアルゴリズムを実装します。
d = 3
c = 3
primes = []
primes.append(2)
isPrime = []
N=20
cnt = 0
# 奇数についてtrue情報を格納する
while(c <= N):
isPrime.append(True)
c += 2
while(d <= N):
if isPrime[((d-1)//2)-1] == True: # (エ)
primes.append(d)
t = d*d
while(t <= N):
isPrime[((t-1)//2)-1] = False # (オ)
print(t)
t += 2*d # (カ)、(L3)
cnt += 1
d += 2
print(primes)
print(cnt)
今回は穴埋め問題が3つあります
穴埋め問題、(エ)について
エについて、今までと同様に対象の値がTrue(素数)であることを記述します。
ただし、ここで一つ気を付けたいのはisPrimeについてです。
今回、偶数を考慮しないためisPrimeは9個しか今回の例だと格納していません。
そのため、d=3の時は、isPrimeの要素番号は1番目
d=5の時は、isPrimeの要素番号は2番目
といった風に対応する必要があります。
よって、d-1を2で割った数をisPrimeの要素番号にします。
答えは以下のようになります
isPrime[(d-1)÷2]がtrueと等しい
穴埋め問題、(オ)について
これもほぼ(エ)と同じ考え方です。
通常の考えだと、tを要素番号を設定しているのですが、今回は偶数を考慮しないため2で割る必要があります。
(t-1)÷2
穴埋め問題、(カ)について
これも2つ目のアルゴリズムを考慮すれば、答えはt+dになります。
ただし、ここで気を付けたいのは今回条件にいずれのループも奇数についてだけ実行するように考慮する必要があります。
tもdも奇数であるため、t+d=奇数+奇数=偶数になるためこの条件に当てはまりません。
そのため、dを2倍にしていつの状態でも奇数になるように調整します。
t+2*d
実行回数を数える(L3)
最後も同様にL3の実行回数を数えるのですが、なんとなくすごく少なそうな気はします。
ひとまず、実行回数結果を下に示します。
9
15
[2, 3, 5, 7, 11, 13, 17, 19]
実行回数
2
今回は2回ですね。
まず、dの初期値は3なのでtには3 * 3で9が入ります。
次に、tに2*d=6を足しますので、tは15になります。
この時点ではまだtは20以下なのでもう一回実行されます。
次にt=15+6=21となるためここでループを抜けます。
よって、実行回数は2回となります。
まとめ
実装すると簡単ですけど、紙で解くと難しく感じる。