2

だから私は素数ファインダーを作ろうとしていて、計算時間を節約するために、1または数値自体ではない除数を見つけたらforloopを中止したい. これで関数は機能しますが、if ステートメントは完全に無視されます。私は何を間違っていますか？

def prime(number):
    oldnum = number
    factor = 1
    while number > 1:
        factor += 1
        while number % factor == 0:
            if 1< factor < oldnum:
                return 0 # is not prime
                print("yay")
                break
            number //= factor
    return 1 #prime!
4

9 に答える 9

4

エラトステネスのふるいを使ってください。素数を見つけるための古くて実績のある方法です:)

于 2013-03-19T08:12:42.453 に答える
3

パフォーマンスの改善について少しだけコメントしますが、要因のみを確認する必要がありfrom 2 to sqrt(num)ます2 to num。

于 2013-03-19T08:12:12.163 に答える
3

コードが行に到達することはありません (ちなみに、これは である必要があります) return 1。return True

  • あなたのステートメントは内側のループbreakから抜け出すだけですwhile
  • あなたがその前にいるので、そのbreak声明に到達することはありません。return 0

とにかく、内側のwhileループは , である必要がありifます (ループを必要とすることは実際には何もしていないため)。

それを変更すると（そして到達不能なコードを削除すると）、「動作」します（ の誤った結果に加えprime(1)てTrue）、素数を見つける非常に非効率的な方法です。

def prime(number):
    oldnum = number
    factor = 1
    while number > 1:
        factor += 1
        if number % factor == 0:
            if 1 < factor < oldnum:
                return False # is not prime
            number //= factor
    return True # is prime!
于 2013-03-19T08:06:46.350 に答える
1

この機能はどうですか？ 

import math

def prime(number):
  if number == 1:
    return 1
  for i in range(2, int(math.sqrt(number)) + 1):
    if number % i == 0:
      return 0
  return 1

于 2013-03-19T08:11:38.997 に答える
1

あなたの最終的な目的は素数を効果的に見つけることであり、他の人はコーディングの問題に非常によく答えているので、より効率的に行う方法について他の回答よりも少し詳しく説明します.

エラトステネスのふるいは、最大 1000 万個までの素数を見つける最速の方法です。nしかし、与えられた数だけが素数かどうかを判断したいようです。

ある数値が素数かどうかを確認するには、以下の素数で割り切れるnかどうかを確認するだけで済みます。したがって、この方法を使用すると、関数で最大 1 億の数を処理する場合、最大 10000 (1229 個の素数) までのすべての素数のリストを準備するだけでよく、これにかかる時間はごくわずかです。sqrt(n)

興味があれば、ここに私の sieve の実装を入れることができますが、あなたはこの問題を自分の娯楽のために解決しているのではないかと思います。

于 2013-03-19T10:07:31.410 に答える
0

これを試してください（エラトステネスのふるいの実装）。

def squares_till(n):
    def square_add(i,n):
        j = i**2
        while j < n:
            yield j
            j = j + i
    A = [True]*n
    A[0] = A[1] = False
    for i in range(2,int(n**0.5)):
        if A[i]:
            for j in square_add(i,n):
                A[j] = False
    return [num for num in range(n) if A[num]]
于 2013-03-19T09:32:08.867 に答える
0

上記の答えに同意します。数値xは、因子1とそれ自体しかない場合、素数であると言われます...理想的な方法は、2から天井関数（sqrt（x））までの因子があるかどうかを確認することです。 ..ここで、天井関数（n）は、n以上の最小の整数を指します。

Cの関数は次のようになります...

//関数は戻ります..{->-1は素数でも合成数でもありません..->0は合成数です..->1は素数です..}

....................................。

 boolean isPrime(int n){

     if(n<=1){
       return -1;
     }else{
      for(int i=2;i<Math.sqrt(n);i++){
        if(n%i==0)
         return 1;
      }
      return 0;
     }
    }
于 2013-03-19T09:01:21.533 に答える
0

これは非常に効率的な実装だと思います。Primality テスト (O(1) 実装) を組み込むことでさらに改善される可能性があります。

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>

using namespace std;

void printN(const vector<int> container, int count, ostream& out=cout, const string& delim=", ") {
    for(int i=0; i<count; ++i)
        out << container[i] << delim;
    out << endl;
}

void printNPrimes(int count) {
    static const int FIRST_PRIME = 2;
    static vector<int> primes(1, FIRST_PRIME);
    static int rangeEnd = 3;

    if(primes.size() >= count) {
        printN(primes, count);
        return;
    }

    int remainingPrimeNumbers = count - primes.size();

    while(remainingPrimeNumbers) {
        bool is_prime = true;
        for(int prime : primes) {
            if(rangeEnd % prime == 0) {
                is_prime = false;
                break;
            }
        }

        if(is_prime) {
            primes.push_back(rangeEnd);
            --remainingPrimeNumbers;
        }

        ++rangeEnd;
    }

    printN(primes, count);
}

int main(int argc, const char *argv[])
{
    if(argc < 2) {
        cout << "usage: rund <count>";
        return -1;
    }

    int count = atoi(argv[1]);
    printNPrimes(count);
    return 0;
}
于 2015-05-12T12:46:11.157 に答える
0

Tim が指摘しているように、if になるには内側の while が必要です。このようなものは機能します（ただし、ひどく非効率的です）

def prime(number):
    oldnum = sqrt(number)
    factor = 1
    while factor <= oldnum:
        factor += 1
        if number % factor == 0 :
            return 0 # is not prime
    return 1 #prime!
于 2013-03-19T08:13:56.900 に答える