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

只需使用Erathostenes 的筛子。这是一种古老且经过验证的寻找素数的方法:)

于 2013-03-19T08:12:42.453 回答
3

您的代码永远不会到达该行return 1（顺便说一句，应该是return True），因为

  • 你的break陈述只会打破内while循环
  • 从未达到过该break声明，因为您return 0在那之前。

无论如何，你的内部while循环应该是一个if（因为你实际上并没有做任何需要循环的事情）。

如果您更改它（并删除无法访问的代码），它会“工作”（除了 be 的错误结果），这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 回答
3

只是稍微评论一下性能的提高，你只需要检查因素from 2 to sqrt(num)，而不是2 to num。

于 2013-03-19T08:12:12.163 回答
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)

如果您有兴趣，我可以将我的筛子实现放在这里，但我猜您正在解决这个问题是为了您自己的娱乐，所以我将留给您。

于 2013-03-19T10:07:31.410 回答
0

正如蒂姆指出的那样，你需要内在的时间来成为一个如果。像这样的东西会起作用（但效率极低）

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 回答
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

试试这个（埃拉托色尼筛法的实施）。

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

我相信，这是非常有效的实施。通过合并 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 回答