遇到小于 n 的简单计数素数问题
Having trouble with simple count primes smaller than n problem
我一直在尝试 leetcode 问题 204(计算小于 n 的素数),但我一直收到 "heap-use-after-free" 错误。我的解决方案如下。我已经添加了一些打印语句来了解正在发生的事情,但它并没有真正帮助。
#include <iostream>
#include <vector>
using namespace std;
int countPrimes(int n) {
if (n < 2) return 0;
vector<int> primes;
primes.push_back(2);
for (int m = 3; m < n; m++) {
cout << "m = " << m << endl;
for (auto it = primes.begin(); it < primes.end(); it++) {
cout << *it << ", ";
}
cout << endl;
bool prime = true;
for (int d : primes) {
cout << "d = " << d << endl;
if (m % d == 0) {
prime = false;
break;
}
cout << "end m = " << m << endl;
if (prime) primes.push_back(m);
}
}
return primes.size();
}
int main() {
cout << countPrimes(9) << endl;
}
打印输出:
m = 3
2,
d = 2
end m = 3
m = 4
2, 3,
d = 2
m = 5
2, 3,
d = 2
end m = 5
d = 0
exit status -1
任何想法我做错了什么。这让我觉得我对我所做的事情有一些根本性的误解...
问题就在这里
bool prime = true;
for (int d : primes) {
...
if (prime) primes.push_back(m);
}
如果循环还更改向量的大小,则不能在向量上使用基于范围的 for 循环。基于范围的 for 循环取决于向量的迭代器,如果向向量添加元素,向量的所有迭代器都会失效。
当然你真的想写这段代码
bool prime = true;
for (int d : primes) {
...
}
if (prime)
primes.push_back(m);
这很好,因为向量是在循环之后修改的,而不是在循环期间。
教训是要严格控制代码的缩进方式。如果您始终正确缩进,则很容易发现错位的代码行。
我一直在尝试 leetcode 问题 204(计算小于 n 的素数),但我一直收到 "heap-use-after-free" 错误。我的解决方案如下。我已经添加了一些打印语句来了解正在发生的事情,但它并没有真正帮助。
#include <iostream>
#include <vector>
using namespace std;
int countPrimes(int n) {
if (n < 2) return 0;
vector<int> primes;
primes.push_back(2);
for (int m = 3; m < n; m++) {
cout << "m = " << m << endl;
for (auto it = primes.begin(); it < primes.end(); it++) {
cout << *it << ", ";
}
cout << endl;
bool prime = true;
for (int d : primes) {
cout << "d = " << d << endl;
if (m % d == 0) {
prime = false;
break;
}
cout << "end m = " << m << endl;
if (prime) primes.push_back(m);
}
}
return primes.size();
}
int main() {
cout << countPrimes(9) << endl;
}
打印输出:
m = 3
2,
d = 2
end m = 3
m = 4
2, 3,
d = 2
m = 5
2, 3,
d = 2
end m = 5
d = 0
exit status -1
任何想法我做错了什么。这让我觉得我对我所做的事情有一些根本性的误解...
问题就在这里
bool prime = true;
for (int d : primes) {
...
if (prime) primes.push_back(m);
}
如果循环还更改向量的大小,则不能在向量上使用基于范围的 for 循环。基于范围的 for 循环取决于向量的迭代器,如果向向量添加元素,向量的所有迭代器都会失效。
当然你真的想写这段代码
bool prime = true;
for (int d : primes) {
...
}
if (prime)
primes.push_back(m);
这很好,因为向量是在循环之后修改的,而不是在循环期间。
教训是要严格控制代码的缩进方式。如果您始终正确缩进,则很容易发现错位的代码行。