java - 埃拉托斯特尼筛法问题java

Question

我正在尝试制作埃拉托斯特尼筛，我目前遇到了问题。问题是在计算过程中，程序不会继续到下一个素数。我认为问题出在 while 循环上，但我不知道如何解决它。有人可以帮助我吗？

谢谢

import java.util.*;
import java.io.*;

public class Primes_below_N {

    static Vector<Integer> numbers = new Vector<Integer>();
    static BufferedReader br = new BufferedReader(new InputStreamReader(
            System.in));

    public static void main(String[] args) throws IOException {
        System.out.print("Please enter a number: ");
        int LIMIT = Integer.parseInt(br.readLine());
        populate(LIMIT);
        calculatePrimes(LIMIT);
        print(numbers);

    }

    // populate a 'numbers' with a numbers upto limit
    public static void populate(int limit) {
        for (int i = 1; i <= limit; i++) {
            numbers.add(i);
        }
    }

    // calculate prime numbers
    public static void calculatePrimes(int limit) {
        int p = 2;
        int nextPrime = 1;
        while (Math.pow(p, 2) < limit) {
            for (int i = 0; i < numbers.size(); ++i) {
                if (numbers.get(i) % 2 == 0 && numbers.get(i) != i) {
                    numbers.remove(i);
                }
            }
            p = numbers.get(nextPrime);
            nextPrime += 1;
        }
    }

    public static void print(Vector<Integer> list) {
        for (int i : list) {
            System.out.println(i);
        }
    }

}

Answer 1

问题出在这两行:

• if (numbers.get(i) % 2 == 0 &&numbers.get(i) != i)

应该是if (numbers.get(i) % p == 0 &&numbers.get(i) != p)

• p = Numbers.get(nextPrime); nextPrime += 1;

顺序应该相反，即nextPrime++; p = Numbers.get(nextPrime);

另外作为旁注:该算法表示创建从 2 到 n 的连续整数列表:(2, 3, 4, ..., n) 而不是来自 (1, 2, .... , n)

<小时/>

我已经复制了您的代码并更改了我之前提到的行(标记为 CHANGE 1 和 CHANGE 2)。

package test;

import java.util.*;
import java.io.*;

import java.util.*;
import java.io.*;

public class Primes_below_N {

    static Vector<Integer> numbers = new Vector<Integer>();
    static BufferedReader br = new BufferedReader(new InputStreamReader(
            System.in));

    public static void main(String[] args) throws IOException {
        System.out.print("Please enter a number: ");
        int LIMIT = Integer.parseInt(br.readLine());
        populate(LIMIT);
        calculatePrimes(LIMIT);
        print(numbers);

    }

    // populate a 'numbers' with a numbers upto limit
    public static void populate(int limit) {
        for (int i = 1; i <= limit; i++) {
            numbers.add(i);
        }
    }

    // calculate prime numbers
    public static void calculatePrimes(int limit) {
        int p = 2;
        int nextPrime = 1;
        while (Math.pow(p, 2) < limit) {
            for (int i = 0; i < numbers.size(); ++i) {

                // CHANGE 1 - IF block change
                if (numbers.get(i) % p == 0 && numbers.get(i) != p) {
                    numbers.remove(i);
                }
            }

            // CHANGE 2 - Reorder
            nextPrime += 1; 
            p = numbers.get(nextPrime);

        }
    }

    public static void print(Vector<Integer> list) {
        for (int i : list) {
            System.out.print(i + ", "); // Changed for single line printing
        }
    }

}

测试1

>>输入: 请输入数字:50

>>输出: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,

由于您的代码，有人会来。

测试2

>>输入: 请输入数字:100

>>输出: 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,

如您所见，100 有 25 个素数(不包括 1)