在 C 中修改质数筛 [英] Modifying the Prime Number Sieve in C
问题描述
网上有许多埃拉托色尼筛法的实现.通过谷歌搜索，我发现
为了匹配作者提供的伪代码，我修改了上面的原程序并写了
#include #include #define limit 10/*整数数组的大小*/int main(){unsigned long long int i,j,k;int *素数；int *arr[100];整数 z = 1;素数 = malloc(sizeof(int) * limit);for (i = 2;i < limit; i++)素数[i] = 1;for (i = 2;i < limit; i++)如果(素数[i])for (j = i;i * j 哪个返回
k 到 k^2 范围内的质数是:元素[10] = 10元素[14] = 14元素[15] = 15元素[16] = 16元素[17] = 17元素[18] = 18元素[19] = 19...这显然是错误的.我认为我的错误在于我对伪代码的解释
作为
for (k=limit; k 因为我是 C 的新手，所以我可能犯了一个基本错误.我不确定上面的五行代码有什么问题，因此在 Stack Overflow 上提出了一个问题.
你的循环语句有问题，j 变量应该用于 primes 的索引，即指向值为 0 或 1 的 int 数组的指针.在这种情况下，您可以使用 primes 数组是算法中的 S(k).
for (k=limit; k 所以带有 j 的 for 循环应该是
for (j = 2; j and condition IN if 语句应该是
if (primes[j] && (k % j) == 0){arr[k] = 0;休息;}如果这个条件为真，我们应该用 j 变量退出内部 for 循环.在带有j 的for 循环之外，应该检查j 变量的值以检查内部循环是否完成(j == limit).
if (j == limit) arr[k] = 1;这里是我修改的整个 for 循环(外循环和内循环).
for (k = limit; k 这里是完整的解决方案:
#include #include #define limit 10/*整数数组的大小*/int main() {unsigned long long int i, j, k;int *素数；int arr[限制*限制]；整数 z = 1;素数 = (int*)malloc(sizeof(int) * limit);for (i = 2; i < limit; i++)素数[i] = 1;for (i = 2; i < limit; i++)如果(素数[i])for (j = i; i * j There are many implementations of the Sieve of Eratosthenes online. Through searching Google, I found 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;
}
I then attempted to update the existing code so that the C program would follow what is described by Scott Ridgway in Parallel Scientific Computing. In the first chapter, the author describes what is known as the Prime number sieve. Instead of finding the primes up to a number k, the modified sieve searches for primes between k <= n <= k^2. Ridgway provides the psuedocode to write this algorithm.
To match the psuedocode provided by the author, I modified the original program above and wrote
#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;
}
which returns
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
.
.
.
This is clearly wrong. I think that my mistake is in my interpretation of the psuedocode
as
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;
As I am new to C, I likely made an elementary mistake. I'm not sure what is wrong with the five lines of code above and have therefore asked a question on Stack Overflow.
You have some problem with your loop statement, j variable should use for index of primes that is pointer to array of int with 0 or 1 values. You can use primes array in this case is S(k) in algorithm.
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;
So the for loop with j should be
for (j = 2; j < limit; j++)
And condition IN if statement should be
if (primes[j] && (k % j) == 0)
{
arr[k] = 0;
break;
}
And if this condition is true, we should exit inner for loop with j variable. Outside for loop with j, should check value of j variable to check if the inner loop is completed or not (j == limit).
if (j == limit) arr[k] = 1;
So here is the entire for loop (outer and inner loop) the I modified.
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;
}
And here is entire solution:
#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 中修改质数筛的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
