我在MSVC中使用布尔向量编写eratosthenes算法的筛子(因为我打算通过用户输入使数组/向量动态)
我的代码:
#include<iostream>
#include<cmath>
#include<vector>
void sieve(std::vector<bool>& prime)
{
long long size = prime.size();
long long sq = (long long)sqrt(size);
if (size >= 2)
prime[0] = prime[1] = false;
for (long long i = 2; i <= sq; ++i)
if (prime[i])
for (long long j = i*i; j <= size; j += i)
prime[j] = false;
}
int main()
{
int m, n;
std::cout << "Enter first number: ";
std::cin >> m;
std::cout << "Enter second number: ";
std::cin >> n;
std::vector<bool> prime(n, true);
sieve(prime);
for (long long i = m; i <= n; ++i)
if (prime[i])
std::cout << i << std::endl;
}
我在MSVC 中偶然发现了一个运行时错误
MSVC错误
但是,当使用g++编译时,此代码可以完美地工作。我不知道怎么了。任何帮助都将是可观的
感谢
for (long long i = m; i <= n; ++i)
和for (long long j = i*i; j <= size; j += i)
都将经过矢量的末尾,因为vector_name[vector_size]
是1,经过矢量中元素的末尾。这是未定义的行为,你很不幸它在g++上起作用。有些人从不费心在另一个编译器上进行编译,看看他们是否得到了相同的结果。如果你没有,你的"工作代码"中就会出现一个无声的错误。
将循环更改为for (long long i = m; i < n; ++i)
和for (long long j = i*i; j < size; j += i)
,您将不再跑过矢量的末尾。
for (long long j = i*i
prime[j] = false;
这是你的问题,位置大于你的向量大小。
我注意到的另一件事是,向量的大小应该是n*n
:
std::vector<bool> prime(n*n, true);
void sieve(std::vector<bool>& prime,int m,int n)
{
long long size = prime.size();
// long long sq = (long long)sqrt(size); you can use n for this so you don't have to make another variable.
if (size >= 2)
prime[0] = prime[1] = false;
for (long long i = m; i < n; ++i)
{
if (prime[i])
{
for (long long j = i*i; j < n*n; j += i)
{
prime[j] = false;
}
}
}
}
int main()
{
int m, n;
std::cout << "Enter first number: ";
std::cin >> m;
std::cout << "Enter second number: ";
std::cin >> n;
std::vector<bool> prime(n*n, true);
sieve(prime,m,n);
for (long long i = m; i <= n; ++i)
{
if (prime[i])
{
std::cout << i << std::endl;
}
}
}
这应该有效;),并且不要忘记包括标题。