4

私は問題を解決しています：

最初の 6 つの素数 (2、3、5、7、11、13) をリストすると、6 番目の素数が 13 であることがわかります
。10 001 番目の素数とは何ですか?

def checkPrime(x):
    facs = 0
    for i in range(1,x):
        if x%i==0:
            facs = facs + 1
    if facs == 2:
        return True
    else :
        return False

i = 1
noPrime = 0
done = False
while(done==False):
    i = i + 1
    print "i = {0} and noPrime={1}".format(i,noPrime)
    if checkPrime(i)==True:
        noPrime = noPrime + 1
        if noPrime==10001 :
            print i
            done=True

しかし、それには多くの時間がかかります。
どうすれば高速化できますか？

4

4 に答える 4

5

素数性テストを使用してそれを行う方法:

def isPrime(n):
    if n == 2: return True
    if n % 2 == 0 or n < 2: return False
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0: return False
    return True
if __name__ == "__main__":
    n = count = 1
    while count < 10001:
        n += 2
        if isPrime(n): count += 1
    print n

0.2 秒で実行されます。この問題には関係ありませんが、他の人が言ったように、ふるいの方が効率的です。

于 2013-03-14T05:18:30.830 に答える
4

素数定理を使用して、どこまで行かなければならないかをかなり正確に見積もることができます。(プログラム内の配列 p のサイズを見積もります)。pi(n)、 未満の素数の数はn、漸近的にn%^.n(でn除算ln n) なります。10001 番目の素数の方程式は10001=n%^.nであり、これを解くとn1.1e5nと 1.2e5 の間になります。

そのため、チェックする値の範囲を減らして、その範囲の数だけをチェックすることができます。この手法により、プログラムの実行時間が短縮されます。

于 2013-03-14T05:29:33.593 に答える
2

これにはエラトステネスのふるいを使用する必要はありません（ただし、将来問題が発生する可能性があります）。10001素数を見つけるのは比較的速いです。

注意事項：

  • 奇数のみをテストします（＃2を除く）
  • 値の平方根までの除数をテストするだけで済みます。

以下のネタバレ-あなたが問題を解決したと仮定しますが、それはただ長い時間がかかります

C＃の例（申し訳ありませんが、Pythonはわかりません）：

class Program
{
    static bool IsPrime(int value)
    {
        if (value == 2) return true;
        if (value % 2 == 0) return false;

        // Test for divisors up to the square root of "value", increment by 2.
        for (int i = 3; i <= Math.Sqrt(value); i += 2)
        {
            if (value % i == 0)
                return false;
        }
        return true;
    }

    static void Main(string[] args)
    {
        int primeCount = 1; // #2

        // Test only odd numbers.
        for (int i = 3; ; i += 2)
        {
            if (IsPrime(i))
            {
                primeCount++;
                if (primeCount == 10001)
                {
                    Console.WriteLine(i.ToString());
                    break;
                }
            }
        }
        Console.ReadLine();
    }
}
于 2013-03-14T05:12:43.400 に答える
2

他のみんなが彼らの解決策を投稿していたので、私は単純な除算方法にいくつかの明らかな改善を含めると思いました：

def is_prime(nr):
    if nr < 2: return false
    if nr < 4: return true
    if nr % 2 == 0: return false
    if nr < 9: return true
    if nr % 3 == 0: return false
    for i in range(5, int(nr**0.5) + 1, 6):
        if number % i == 0: return false
        if number % (i + 2) == 0: return false
    return true

これは、1つの不要なモジュロ演算を取り除くことにより、単純なソリューションを改善します。

于 2013-03-14T05:27:17.230 に答える