所以我正在尝试制作一个 C++ 程序来生成所有素数直到某个点,但由于某种原因,它将 2 之后的所有数字打印为非素数。
int A[1000000];
void sieve(int till)
{
for(int i = 2; i < till; i++)
{
if(A[i] == 0)
{
for(int j = i*i; j < till; j+=i)
{
A[j - 1] = 1;
//printf("%i is NOT prime\n", ij);
}
}
}
}
主要是我做的:
int N;
scanf("%i", &N);
sieve(N);
但是当我尝试调试时它说:
NOT PRIME 0
NOT PRIME 1
NOT PRIME 2
PRIME 3
NOT PRIME 4
PRIME 5
NOT PRIME 6
PRIME 7
NOT PRIME 8
PRIME 9
NOT PRIME 10
PRIME 11
NOT PRIME 12
NOT PRIME 13
谁能知道我做错了什么?
编辑:A int 表自动初始化为 0,因为它在主类之外。
最佳答案
非常简单。我们有几个小案例:
- 0 多于两个除数,所以它不是质数
- 1 只有一个约数,所以它不是质数
- 2是唯一的素数偶数
所以,基本上我们不应该计算偶数。我们只对奇数感兴趣。
我们会将所有非质数标记为 1。
int A[1000000];
void sieve(int till)
{
// mark all even numbers (except 2) as not prime
for(int i = 4; i < till; i += 2)
{
A[i] = 1;
}
// now calculate not primes for only odd numbers
for(int i = 3; i < till; i += 2 )
{
if(A[i] == 0)
{
for(int j = i*i; j < till; j+=(i+i))
{
A[j] = 1;
}
}
}
}
int main()
{
int N;
scanf("%i", &N);
sieve(N);
for(int i = 2; i < N; i++)
{
if(A[i] == 1) printf("%d is not prime\n", i);
else printf("%d is prime\n", i);
}
return 0;
}
关于c++ - 埃拉托色尼筛法 C++ 不起作用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39556837/