我正在尝试使用集合来计算素数,但是当我进行计算时,我的迭代器正在随机跳跃。
我正在尝试为 N=10 的值实现此方法。
Choose an integer n. This function will compute all prime numbers up to n. First insert all numbers from 1 to n into a set. Then erase all multiples of 2 (except 2); that is, 4, 6, 8, 10, 12, .... Erase all multiples of 3, that is, 6, 9, 12, 15, ... . Go up to sqrt(n) . The remaining numbers are all primes.
当我运行代码时,它会删除 1,然后 pos 跳转到 4?我不知道为什么会发生这种情况,而不是转到值 2,即集合中的第二个值?
此外,当我删除迭代器指向的值后会发生什么,迭代器指向什么,如果我将其推进到哪里?
这是代码:
set<int> sieveofEratosthenes(int n){ //n = 10
set<int> a;
set<int>::iterator pos = a.begin();
//generate set of values 1-10
for (int i = 1; i <= n; i++) {
a.insert(i);
if(pos != a.end())
pos++;
}
pos = a.begin();
//remove prime numbers
while (pos != a.end())
{
cout << "\nNew Iteration \n\n";
for (int i = 1; i < sqrt(n); i++) {
int val = *pos%i;
cout << "Pos = " << *pos << "\n";
cout << "I = " << i << "\n";
cout << *pos << "/" << i << "=" << val << "\n\n";
if (val == 0) {
a.erase(i);
}
}
pos++;
}
return a;
}
最佳答案
您的实现是不正确的,因为它试图将筛算法与尝试除数的简单算法结合起来,但没有成功。您不需要测试整除性来实现筛子 - 事实上,这是算法之美的主要贡献者!您甚至不需要乘法。
a.erase(1);
pos = a.begin();
while (pos != a.end()) {
int current = *pos++;
// "remove" is the number to remove.
// Start it at twice the current number
int remove = current + current;
while (remove <= n) {
a.erase(remove);
// Add the current number to get the next item to remove
remove += current;
}
}
关于c++ - 使用集合计算素数,C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34422942/