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

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这样更大的数字，这将产生不正确的结果。List = [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);

你的代码将返回231个素数，而实际上只有168个素数。这是因为你没有考虑未来的质数，这些质数只能被7到该数之间的质数整除。

例如:121将被您作为质数返回，但它是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);

你可以在这里看到一个更快的模式。找到质数最快的算法是什么?