関数の可用性を想定しますis_prime。変数 n が正の整数に関連付けられているとします。最初の n 個の素数の合計を計算するために必要なステートメントを記述します。合計は、変数の合計に関連付ける必要があります。
注: is_primeパラメータとして整数を取り、Trueその整数が素数である場合にのみ戻ります。さて、私はis_primeこのような関数を書きました：
def is_prime(n):
n = abs(n)
i = 2
while i < n:
if n % i == 0:
return False
i += 1
return True
ただし、n==0 以外は機能します。すべての整数に対して機能するように修正するにはどうすればよいですか? 最初のn個の素数の合計を取得する関数を作成する方法と、正の数だけでなく、可能なすべての入力に対して機能するis_prime関数を変更する方法の両方の答えを見つけようとしています。
あなたの任務は次のとおりです。
関数 is_prime が使用可能であると仮定します。変数 n が正の整数に関連付けられているとします。最初の n 個の素数の合計を計算するために必要なステートメントを記述します。合計は、変数の合計に関連付ける必要があります。
NVRAM がコメントで正しく指摘しているように (そして、他の誰も理解していないようです)、質問には「機能の可用性を想定する」と記載されていますis_prime。
その関数を書く必要はありません。あなたがしなければならないことは、「最初のn個の素数の合計を計算するために必要なステートメントを書く」ことです。
そのための擬似コードは次のようになります。
primes_left = n
curr_num = 2
curr_sum = 0
while primes_left > 0:
if is_prime(curr_num):
curr_sum = curr_sum + curr_num
primes_left = primes_left - 1
curr_num = curr_num + 1
print "Sum of first " + n + " primes is " + curr_sum
選択した言語でその疑似コードを実装するだけでよいことがわかると思います。
割り当てをテストするために の実装を探している場合is_prime、それがどれほど効率的であるかは問題ではありません。とにかくいくつかの小さな値をテストするだけだからです。また、それを使用するコードの制約を考えると、2 未満の数について心配する必要はありません。このようなものは完全に受け入れられます:
def is_prime(num):
if num < 2:
return false
if num == 2:
return true
divisor = 2
while divisor * divisor <= num:
if num % divisor == 0:
return false
divisor = divisor + 1
return true
問題文では、n は正の整数であると書かれています。したがってassert(n>0)、プログラムの外側のループがis_prime()負の値でもゼロでもないことを確認してください。
あなたのアルゴリズム - 連続するすべての奇数の試行分割(「奇数」はあなたにとって大きなスピードアップになります) - は機能しますが、非常に遅くなります。インスピレーションを得るために、プライムシーブを見てください。
では、n が 0 または 1 の場合はどうなるでしょうか。
あなたが持っている
i = 2
while i < n: #is 2 less than 0 (or 1?)
...
return True
0 または 1 の n を返すようFalseにしたい場合、これらのケースを考慮して条件 (または関数自体) を変更する必要があることを示唆していませんか?
i = 0 または 1 の答えをハードコーディングしないのはなぜですか?
n = abs(n)
i = 2
if(n == 0 || n == 1)
return true //Or whatever you feel 0 or 1 should return.
while i < n:
if n % i == 0:
return False
i += 1
return True
また、いくつかの数値を省略することで、アルゴリズムの速度をさらに向上させることができます。このスクリプトは n の平方根までしかチェックしません。これは、ある数に 1 つ以上の因数がある場合、その平方根よりも大きな因数を持つ合成数がないためです。多数をテストする場合、これはかなり大きな違いになります。
n = abs(n)
i = 2
if(n == 0 || n == 1)
return true //Or whatever you feel 0 or 1 should return.
while i <= sqrt(n):
if n % i == 0:
return False
i += 1
return True
これを試して：
if(n==0)
return true
else
n = abs(n)
i = 2
while i < n:
if n % i == 0:
return False
i += 1
return True