在线有许多埃拉托斯特尼筛法的实现。通过Google搜索,我发现this implementation in C .
#include <stdio.h>
#include <stdlib.h>
#define limit 100 /*size of integers array*/
int main(){
unsigned long long int i,j;
int *primes;
int z = 1;
primes = malloc(sizeof(int) * limit);
for (i = 2;i < limit; i++)
primes[i] = 1;
for (i = 2;i < limit; i++)
if (primes[i])
for (j = i;i * j < limit; j++)
primes[i * j] = 0;
printf("\nPrime numbers in range 1 to 100 are: \n");
for (i = 2;i < limit; i++)
if (primes[i])
printf("%d\n", i);
return 0;
}
然后,我尝试更新现有代码,以便 C 程序遵循 Scott Ridgway 在 Parallel Scientific Computing 中描述的内容。 。在第一章中,作者描述了所谓的素数筛。修改后的筛子不是查找 k 以内的素数,而是搜索 k <= n <= k^2 之间的素数。 Ridgway 提供了编写该算法的伪代码。
为了匹配作者提供的伪代码,我修改了上面的原始程序并编写了
#include <stdio.h>
#include <stdlib.h>
#define limit 10 /*size of integers array*/
int main(){
unsigned long long int i,j,k;
int *primes;
int *arr[100];
int z = 1;
primes = malloc(sizeof(int) * limit);
for (i = 2;i < limit; i++)
primes[i] = 1;
for (i = 2;i < limit; i++)
if (primes[i])
for (j = i;i * j < limit; j++)
primes[i * j] = 0;
/* Code which prints out primes for Sieve of Eratosthenes */
/*printf("\nPrime numbers in range 1 to 100 are: \n");
for (i = 2;i < limit; i++)
if (primes[i])
//printf("Element[%d] = %d\n", i, primes[i]);*/
for (k=limit; k < limit*limit; k++)
for (j = primes[0]; j = arr[sizeof(arr)/sizeof(arr[0]) - 1]; j++)
if ((k % j) == 0)
arr[k]=0;
arr[k] = 1;
printf("\nPrime numbers in range k to k^2 are: \n");
for (k=limit; k < limit*limit; k++)
if (arr[k])
printf("Element[%d] = %d\n", k, k);
return 0;
}
返回
Prime numbers in range k to k^2 are:
Element[10] = 10
Element[14] = 14
Element[15] = 15
Element[16] = 16
Element[17] = 17
Element[18] = 18
Element[19] = 19
.
.
.
这显然是错误的。我认为我的错误在于我对伪代码的解释
作为
for (k=limit; k < limit*limit; k++)
for (j = primes[0]; j = arr[sizeof(arr)/sizeof(arr[0]) - 1]; j++)
if ((k % j) == 0)
arr[k]=0;
arr[k] = 1;
由于我是 C 语言新手,我可能犯了一个基本错误。我不确定上面的五行代码有什么问题,因此在 Stack Overflow 上提出了一个问题。
最佳答案
您的循环语句存在一些问题,j
变量应该用于 primes
的索引,该索引是指向具有 0 或 1 值的 int 数组的指针。您可以使用primes
数组,这种情况下是算法中的S(k)。
for (k=limit; k < limit*limit; k++)
for (j = primes[0]; j = arr[sizeof(arr)/sizeof(arr[0]) - 1]; j++)
if ((k % j) == 0)
arr[k]=0;
arr[k] = 1;
因此带有 j
的 for 循环应该是
for (j = 2; j < limit; j++)
并且条件 IN if
语句应该是
if (primes[j] && (k % j) == 0)
{
arr[k] = 0;
break;
}
如果这个条件为真,我们应该使用 j
变量退出内部 for 循环。在带有 j
的 for 循环之外,应检查 j
变量的值,以检查内部循环是否完成(j == limit)
。
if (j == limit) arr[k] = 1;
这是我修改的整个 for 循环(外部和内部循环)。
for (k = limit; k < limit*limit; k++)
{
for (j = 2; j < limit; j++)
{
if (primes[j] && (k % j) == 0)
{
arr[k] = 0;
break;
}
}
if (j == limit) arr[k] = 1;
}
这是完整的解决方案:
#include <stdio.h>
#include <stdlib.h>
#define limit 10 /*size of integers array*/
int main() {
unsigned long long int i, j, k;
int *primes;
int arr[limit*limit];
int z = 1;
primes = (int*)malloc(sizeof(int) * limit);
for (i = 2; i < limit; i++)
primes[i] = 1;
for (i = 2; i < limit; i++)
if (primes[i])
for (j = i; i * j < limit; j++)
primes[i * j] = 0;
/* Code which prints out primes for Sieve of Eratosthenes */
/*printf("\nPrime numbers in range 1 to 100 are: \n");
for (i = 2;i < limit; i++)
if (primes[i])
//printf("Element[%d] = %d\n", i, primes[i]);*/
for (k = limit; k < limit*limit; k++)
{
for (j = 2; j < limit; j++)
{
if (primes[j] && (k % j) == 0)
{
arr[k] = 0;
break;
}
}
if (j == limit) arr[k] = 1;
}
printf("\nPrime numbers in range k to k^2 are: \n");
for (k = limit; k < limit*limit; k++)
if (arr[k] == 1)
printf("Element %d\n", k);
return 0;
}
关于c - 用 C 修改素数筛,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54964020/