质数 - 我需要澄清代码实现

Question

这是我知道的代码：

bool checkPrime(int n) {
    bool prime = true;

    for (int i = 2; i < n; i++) {
        if ((n%i) == 0) {
            prime = false;
        }
    }
    return prime;
}

但是，如果您正在寻找素数，这样可以吗：

List<int> arr = [2, 3, 5, 7]; // Already known

int n = 30; // Between 1 to 30. It could be any number

for (int i = 2; i < n; i++) {
    if (i % 2 != 0 && i % 3 != 0 && i % 5 != 0 && i % 7 != 0) {
        arr.add(i);
    }
    // Then maybe some code for numbers less than 8
}

print(arr);

输出：

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

而且时间复杂度也有很大差异吗？

Answer 1

您的代码不正确。此代码之所以有效，是因为您将 n 的值设为 30，对于更大的数字（如 1000），这将产生不正确的结果。列表 arr = [2,3,5,7]; // 已知

int n = 1000; // between 1 to 1000 it could be any number
List<int> arr = [2,3,5,7];

for (int i = 2; i < n; i++) {
    if (i % 2 != 0 && i % 3 != 0 && i % 5 != 0 && i % 7 != 0){
        arr.add(i);
    }
    //Then maybe some code for numbers less than 8
}
  
print(arr);

当实际上只有 168 个质数时，您的代码将 return 231 个质数。这是因为你没有考虑只能被7到那个数之间的一个质数整除的未来质数

例如：121 将被您 return 编辑为质数，但它是 11

的倍数

扩展你的模式。虽然这会更快，因为它减少了一些除法运算，但由于有两个循环，它仍然是 N 平方。

这里我只是简单地从现有素数集合中除数，如果发现下一次迭代使用素数进行除法，则将它们添加到集合中。

  List < int > arr = [2]; // taking 2 since this is the lowerst value we want to start with 
    
    int n = 30; // n can between 2 to any number
    if (n < 3) {
    
        print(arr); // can return from here.
    }
    // since we already have added 2 in the list we start with next number to check that is 3
    for (int i = 3; i < n; i++) {
        bool isPrime = true;
        for (int j = 0; j < arr.length; j++) { // we iterate over the current prime number collection only [2] then [2,3]...
            if (i % arr[j] == 0) { // check if number can be divided by exisiting numbers
                isPrime = false;
            }
        }
    
        if (isPrime) { // eg: 2 cant divide 3 so we 3 is also added 
            arr.add(i)
        }
    
    }
    
    print(arr);

您可以在此处查看更快的模式。 Which is the fastest algorithm to find prime numbers?

质数 - 我需要澄清代码实现

Prime numbers - I need clarification on code implementation

c++

java

primes