Eratosthenes 筛法，素数 C

Question

我正在编写一个程序来查找直到 1000 的素数，使用埃拉托色尼筛法...但它不起作用...这是我的全部代码，但是 "calculation"找到函数内的素数 "markPrimes"（我有信心说其余代码没问题，所以我很确定问题出在这个函数中...

#include <stdio.h>
#include <stdlib.h>

typedef struct primal
{
    int number; /* a number */
    char mark;  /* flag marking the number as active (1) or inactive (0) */
} primal;


void initialize(primal *s,int size)
{
    int i;
    for(i=0;i<1000;i++)
    {
        s[i].number=i+1;
        s[i].mark=1; //1=prime number 
    }
}

void markPrimes(primal *s,int size)
{
    /* add this function - it should mark all of the numbers in the passed primal array that are not prime numbers as inactive */
    //Brute Sieve of Eratosthenes Approach (0=not prime number)

    s[0].mark=0; //s[0].number=1 as on the function "initialize" I start from 1 not from 0
    int i,j;
    for (unsigned i = 2; i*i <size; i++)
    {
        if (s[i].mark == 1)
            for (unsigned j = i<<1;j<size;j+=i)
                s[j].mark = 0;
    }
}

int main(void)
{
    int i,j,prime_numbers[200];
    primal source_numbers[1000]; /* an array of source values */

    for(i=0;i<200;i++) prime_numbers[i]=0; /* initialize the prime numbers array to 0 */

    initialize(source_numbers,1000); /* initialize the source numbers array to hold the numbers 1-1000 */

    markPrimes(source_numbers,1000); /* identify the prime numbers in the source numbers array */

    /* copy the primes from the source numbers to the prime numbers array */
    for(i=0,j=0;i<1000;i++)
    {
        if(source_numbers[i].mark==1) /* if the current source number is a prime */
        {
            prime_numbers[j]=source_numbers[i].number; /* copy the number */
            j++; /* increment the target index */
        }
    }

    /* print the prime numbers */
    for(i=0,j=0;prime_numbers[i]!=0;i++,j++)
    {
        printf("%3d ",prime_numbers[i]);
        if(j==9) /* periodically print a newline and then reset j */
        {
            printf("\n");
            j=-1;
        }
    }
    return 0;
}

Answer 1

埃拉托色尼筛法的起点存在问题。

for (unsigned i = 1; i*i

这个循环应该从 2 而不是 1 开始。您基本上所做的是最初将所有数字标记为非素数。

相反，通过执行 s[0].mark=0; 手动将 0 和 1 标记为非素数； s[1].标记=1。然后从 i=2

开始循环

Answer 2

众所周知，C 允许程序员在他们的脚上打点（别担心，我们每个人都有这样的伤疤），这就是这里发生的事情。

在你的内循环中，你从1开始而不是0，所以你需要将实际数字减一作为索引并添加该数字而不是索引：

void markPrimes(primal *s,int size)
{
    //Brute Sieve of Eratosthenes Approach (0=not prime number)

    int i,j;
    // 1 (one) is not prime per definition
    s[0].mark = 0;
    for (i = 1; i*i <size; i++)
    {;
        if (s[i].mark == 1) {
            // you start at 1 instead of 0, so you need to take the actual number
            // minus one as the index and add that number instead of the index.
            for ( j = 2 * s[i].number  - 1;j < size; j += s[i].number){
                s[j].mark = 0;
            }
        }
    }
}

Eratosthenes 筛法，素数 C

Sieve of Eratosthenes, Prime Numbers C

c

math

primes

numbers