用链表筛选素数

Question

我正在尝试专门使用筛选素数方法从列表中删除任何非素数的数字。我有一个我一直在研究的程序，到目前为止我在列表中没有任何素数，但我最终也删除了一些素数，如 17 和 29 等。*注意我只删除了的倍数2 到 32。这是我的代码。

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
    int data;
    struct node *next;
}node;
node *Inserttail(node *head, int x){
    node *temp = (node*)malloc(sizeof(node));
    temp->data = x;
    temp->next = NULL;
    node *temp1 = head;
    if(head==NULL)
        return temp;
    else if(head->next ==NULL){
        head ->next = temp;
        return head;
    }
    while(head->next != NULL)
        head = head->next;
    head->next = temp;
    return temp1;
}
void Print(node *head){
    while(head != NULL){
        printf(" %d", head->data);
        head = head ->next;
    }
}
node *Deletemultiples(node *head, int k){
    node *temp = head, *old = temp;
    int i = 1;
    while(temp!=NULL){
        if(i%k==0 && i!= k)
            old->next = temp->next;
        old=temp;
        temp= temp->next;
        i++;
    }
    return head;
}
int main(){
    node *head = NULL;
    int i;
    for(i=1; i<=1000; i++)
        head = Inserttail(head, i);
    for(i=2; i<=32; i++)
        head = Deletemultiples(head, i);
    Print(head);
    return 0;
}

这是我现在得到的输出：

 1 2 3 5 7 11 13 19 23 31 35 43 49 59 61 79 83 103 109 119 133 151 155 175 193 211 215 241 259 275 283 323 331 361 373 403 419 443 455 499 511 541 571 613 623 649 673 719 733 781 803 841 871 919 931 991

我现在也在使用的方法对我来说也没有效果，无法从列表中实际释放特定的 link。

Answer 1

在您的 Deletemultiples 函数中，您有以下内容：

int i = 1;
while (temp != NULL) {
   if (i % k == 0 && i != k)
       /* … Other stuff … */

本例中的 i 与您的列表无关，因此您不应该使用它。相反，您想查看 node 结构的 data 成员：

while (temp != NULL) {
    if (temp->data % k == 0 && temp->data != k)

这将为您提供所需的结果：

1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 …

用链表筛选素数

sieve prime numbers with linked list

c

free

primes

linked-list