埃拉托色尼的筛子，产生质数。循环的问题 [英] Sieve of Eratosthenes, generating primes. Problem with loops

问题描述

我正在尝试使用Eratosthenes算法的筛子来生成n个素数。我对它进行了调试，发现在某个时候，它会开始删除已经删除的号码。我不知道出了什么问题，但我敢肯定是我的圈圈出了问题。你能帮帮我吗？

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Part6 {

    public static List<Integer> primeSequence(int n) {
        List<Integer> list = IntStream.range(2, n).boxed().collect(Collectors.toList());

        for (int i = 2; i <= list.size(); i++) {
            for (int j = i + 1; j <= list.size(); j++) {
            if(j % i == 0)
                list.remove(j);
            }
        }
       return  list;
        }


    public static void main(String[] args) {
        System.out.println(primeSequence(Integer.parseInt(args[0])));
    }
    
}

推荐答案

这就是Eratosthenes筛子的工作方式，它始终标记该范围内除其自身以外的所有数字的倍数。
例如，当我们从i=2开始时，我们将4、6、8、10、12、...标记为composite。
同样对于i=3，它将6、9、12、15、...标记为非质数。
请注意6&；12被标记了两次。还有更多的数字会多次标记为复合数字。因此，这是正常的。

现在，上述程序存在以下问题：

1. 当您执行list.remove(j)时，它实际上删除了索引j处的数字，而不是数字j本身。因此，要删除复合数字j，我们需要使用Integer.valueOf(j)
2. 循环的上限不应为list.size()，因为随着我们不断删除数字，列表的大小将不断减小。因此，许多数字将丢失。

下面是您的代码的修改版本：

        for (int i = 2; i < n; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                if (j % i == 0)
                {
                    list.remove(Integer.valueOf(j));
                }
            }
            System.out.println(list);
        }

输入：100
输出：

[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]

这篇关于埃拉托色尼的筛子，产生质数。循环的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！