Sieve of eratosthenes problem java_问答_开发者

I am trying to make sieve of eratosthenes, i am currently having a problem. The probelm is that during the calculation method, the program won't continue to the next prime number. I think the problem is with the while loop but i don't know how to fix it. Can someone help me?

Thank you

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);
        }
    }

}

The problem is with these two line:

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

It should be if (numbers.get(i) % p == 0 && numbers.get(i) != p)

p = numbers.get(nextPrime); nextPrime += 1;

The order should be reverse i.e. nextPrime++; p = numbers.get(nextPrime);

Also as a side note: the algorithm says to Create a list of consecutive integers from two to n: (2, 3, 4, ..., n) and not from (1, 2, .... , n)

I have taken an exact copy of your code and changed the lines which I have mentioned earlier (Marked as 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
        }
    }

}

Test1

>>Input: Please enter a number: 50

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

One is coming because of your code.

Test2

>>Input: Please enter a number: 100

>>Output: 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,

As you can see for 100 there are 25 prime numbers (excluding 1)

I looks like you missed a few points on the algorithm. At face value I'd guess that code is NEVER going to return. WHILE p squared is less than limit DO foreach entry in the list... Nope, never... well not in the lifetime of the universe anyway.

Have a good read through the wikipedia article on the Sieve of Erastothenes: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. It's even got a great visualisation which SHOWS you how the algorithm works.

One issue you will need to address is that as you are applying the sieve, you're removing elements from numbers, and so the indices i and nextPrime aren't pointing where you think they're pointing. It might help you to print console output to the effect