当然、bool isprime(number)クエリできるデータ構造が存在するためです。
私は最良のアルゴリズムを、範囲 (1, N] のメモリ消費量が最も少ないデータ構造を生成するアルゴリズムであると定義します
。ここで、N は定数です。
私が探しているものの単なる例: 私はすべての奇数を表すことができますたとえば、指定された範囲の数値 (1, 10] の場合、3 から始まります。1110
次の辞書はもっと絞り込めますよね？いくつかの作業で 5 の倍数を削除することはできますが、1、3、7、または 9 で終わる数値はビット配列に含まれている必要があります。
問題を解決するにはどうすればよいですか?
一般的な素数テストの最速のアルゴリズムはAKSです。ウィキペディアの記事では、それについて詳しく説明し、元の論文へのリンクを示しています。
大きな数を見つけたい場合は、メルセンヌ素数のような特別な形式を持つ素数を調べてください。
私が通常実装するアルゴリズム (理解しやすく、コーディングしやすい) は次のとおりです (Python の場合):
def isprime(n):
"""Returns True if n is prime."""
if n == 2:
return True
if n == 3:
return True
if n % 2 == 0:
return False
if n % 3 == 0:
return False
i = 5
w = 2
while i * i <= n:
if n % i == 0:
return False
i += w
w = 6 - w
return True
これは、古典的なO(sqrt(N))アルゴリズムの変形です。これは、素数 (2 と 3 を除く) が6k - 1orの形式であるという事実を使用し、6k + 1この形式の約数のみを調べます。
ときどき、本当に速度が必要で範囲が限られている場合は、フェルマーの小定理に基づいて疑似素数検定を実装します。どうしても速度を上げたい (つまり、O(sqrt(N)) アルゴリズムを完全に避ける) 場合は、偽陽性を事前に計算し (カーマイケル数を参照)、二分探索を行います。これは私が今まで実装したテストの中で群を抜いて最速ですが、唯一の欠点は範囲が限られていることです。
数値 N が素数であるかどうかを確認するための非常に単純で簡潔な力ずくのソリューション: 単純に、2 から N の平方根までの N の約数があるかどうかを確認します (興味がある場合は、理由を参照してください)。
次のコードは、Python 2 と Python 3 の両方と互換性があります。
from math import sqrt
from itertools import count, islice
def is_prime(n):
return n > 1 and all(n % i for i in islice(count(2), int(sqrt(n) - 1)))
そして、より単純な Python 3 のみの実装を次に示します。
def is_prime(n):
return n > 1 and all(n % i for i in range(2, int(n ** 0.5) + 1))
わかりやすくするために、上記の拡張バージョンを次に示します。
from math import sqrt
from itertools import count, islice
def is_prime(n):
if n < 2:
return False
for divisor in islice(count(2), int(sqrt(n) - 1)):
if n % divisor == 0:
return False
return True
def is_prime(n):
if n < 2:
return False
for divisor in range(2, int(n ** 0.5) + 1):
if n % divisor == 0:
return False
return True
これは、最速または最適な素数性チェック アルゴリズムに近いものを意図したものではありません。シンプルで簡潔にするという目標を達成するだけであり、実装エラーも減少します。の時間複雑度がありO(sqrt(n))ます。
数値が素数であるかどうかを確認するためのより高速なアルゴリズムを探している場合は、次のことに興味があるかもしれません。
pyprimesieveお気付きかもしれませんが、Python 2 互換の実装では、単純なor ( Python 3 ではデフォルトである古い Python 2ジェネレーターの範囲)の代わりに とitertools.count()組み合わせて使用しています。これは、CPython 2では、N > 2 63 ‒ 1 (または実装によってはN > 2 31 ‒ 1) のような N に対して が発生するためです。これは残念な CPython 実装の詳細です。itertools.islice()range()xrange()xrange(N)OverflowError
itertoolsこの問題を克服するために使用できます。2を使用して から無限大までカウントアップしているため、ステップの後itertools.count(2)に到達し、 を使用してジェネレーターを制限できます。sqrt(n)sqrt(n) - 1itertools.islice()
素数性をテストするための効率的な方法はたくさんありますが（これはそれらの1つではありません）、作成したループはPythonで簡潔に書き直すことができます。
def is_prime(a):
return all(a % i for i in xrange(2, a))
つまり、2とa（包括的ではない）の間のすべての数値がaに分割されたときにゼロ以外の余りを与える場合、aは素数です。
これは、少数のクエリしかない場合に、数値が素数であるかどうかを確認する最も効率的な方法です。多くの数が素数かどうかを尋ねる場合は、エラトステネスのふるいを試してみてください。
import math
def is_prime(n):
if n == 2:
return True
if n % 2 == 0 or n <= 1:
return False
sqr = int(math.sqrt(n)) + 1
for divisor in range(3, sqr, 2):
if n % divisor == 0:
return False
return True
aが素数の場合while x:、コード内の は永久に実行されxますTrue。
では、なぜwhileそこにあるのでしょうか。
因子を見つけたときに for ループを終了したかったと思いますが、方法がわからなかったので、条件があるので while を追加しました。だからここにあなたがそれを行う方法があります：
def is_prime(a):
x = True
for i in range(2, a):
if a%i == 0:
x = False
break # ends the for loop
# no else block because it does nothing ...
if x:
print "prime"
else:
print "not prime"
ウィキペディアによると、エラトステネスのふるいは複雑でメモリO(n * (log n) * (log log n))を必要とするO(n)ため、特に大きな数をテストしていない場合は、開始するのに適しています。
最小メモリ？これは最小ではありませんが、正しい方向への一歩です。
class PrimeDictionary {
BitArray bits;
public PrimeDictionary(int n) {
bits = new BitArray(n + 1);
for (int i = 0; 2 * i + 3 <= n; i++) {
bits.Set(i, CheckPrimality(2 * i + 3));
}
}
public PrimeDictionary(IEnumerable<int> primes) {
bits = new BitArray(primes.Max());
foreach(var prime in primes.Where(p => p != 2)) {
bits.Set((prime - 3) / 2, true);
}
}
public bool IsPrime(int k) {
if (k == 2) {
return true;
}
if (k % 2 == 0) {
return false;
}
return bits[(k - 3) / 2];
}
}
もちろん、 の定義を指定する必要がありますCheckPrimality。
myInp=int(input("Enter a number: "))
if myInp==1:
print("The number {} is neither a prime not composite no".format(myInp))
elif myInp>1:
for i in range(2,myInp//2+1):
if myInp%i==0:
print("The Number {} is not a prime no".format(myInp))
print("Because",i,"times",myInp//i,"is",myInp)
break
else:
print("The Number {} is a prime no".format(myInp))
else:
print("Alas the no {} is a not a prime no".format(myInp))
Java-8 ストリームとラムダの助けを借りて、わずか数行で次のように実装できます。
public static boolean isPrime(int candidate){
int candidateRoot = (int) Math.sqrt( (double) candidate);
return IntStream.range(2,candidateRoot)
.boxed().noneMatch(x -> candidate % x == 0);
}
パフォーマンスはO(sqrt(N))に近いはずです。多分誰かがそれを便利だと思うでしょう。
迅速な検証を行う必要がある場合、入力の平方根よりも小さい数値間の基本的な除算に基づいて、この単純なコードを記述します。
def isprime(n):
if n%2==0:
return n==2
else:
cota = int(n**0.5)+1
for ind in range(3,2,cota):
if n%ind==0:
print(ind)
return False
is_one = n==1
return True != is_one
isprime(22783)
True != n==1はケースを避けることn=1です。