eratosthenes的筛子问题java

我正在努力使eratosthenes筛子，我目前有一个问题。问题是在计算方法中，程序不会继续下一个素数。我认为问题是与while循环，但我不知道如何解决它。有人能帮我吗？eratosthenes的筛子问题java

谢谢

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

}

来源

2011-04-24 Jeel Shah

的问题是与这两个行：

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;

顺序应该是转ERSE即 nextPrime++; p = numbers.get(nextPrime);

另外，作为一个侧面说明：算法说要创建一个从连续两个整数列表到n：（2，3，4，...，N），而不是从（ 1，2，...，n）的

我已代码的精确副本，改变我所前面提到的线（标记为1个CHANGE 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的

>>输入：Please enter a number: 50

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

之一，是因为你的代码来。

的Test2

>>输入：Please enter a number: 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 ）

来源

2011-04-24 03:56:30 Favonius

it still d没有工作，如果你提出的改进。 – 2011-04-24 16:08:53

@ user681159：我早先检查了代码并完全发布。同时检查测试结果。 – Favonius 2011-04-24 16:21:32

我看起来像你错过了算法的几点。在面值时，我猜测代码永远不会返回。尽管p平方小于限制，但是在列表中列出的每一个条目都是......没有，永远......也不在宇宙的一生中。

请仔细阅读Erastothenes筛网上的维基百科文章：http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes。它甚至有一个伟大的可视化，向您展示算法的工作原理。

来源

2011-04-24 03:08:17 corlettk

您需要解决的一个问题是，当您应用筛时，您将从numbers中删除元素，因此索引i和nextPrime未指向您认为他们指向的位置。它可以帮助你在的开始for循环控制台输出打印的效果

System.out.println("Loop index: " + i);

，也

System.out.println("Got prime: " + p);

权获得黄金后。

这听起来像你只是在寻找一个提示，所以我会留下它。

来源

2011-04-24 03:08:25

eratosthenes的筛子问题java

回答

相关问题