为什么我的算法没有给出预期的输出？

我正在尝试创建一个Sieve of Eratosthenes算法的Java实现。为什么我的算法没有给出预期的输出？

我有下面的代码，它运行，虽然给出了一个不正确的输出。

import java.util.ArrayList; 
public class sieveOfEratosthenes { 
    private static final ArrayList<Integer> test = new ArrayList<>(); 
    public static void main (String [] args) { 
     java.util.Scanner tempInput = new java.util.Scanner(System.in); 
     System.out.println("What number would you like the prime numbers to be generated to?"); 
     int maxPrime = tempInput.nextInt(); 
     for(int i = 2; i <= maxPrime; i++) { 
      test.add(i); 
     } 
     getPrimeList(maxPrime); 
    } 

    private static void getPrimeList(int maxNumber) { 
     int sqrtOfNum = (int) Math.sqrt(maxNumber); 
     int temp = 0, i = 0; 
     int currentPrime = test.get(i); 
     boolean completed = false; 
     i++; 
     //do { 
     while((completed == false) && (i < test.size())) { 
      if(i >= test.size()) { 
       completed = true; 
      } else if((temp <= sqrtOfNum)) { 
       removeMultiples(currentPrime); 
      } 
      i++; 
      if (i < test.size()) { 
       currentPrime = test.get(i); 
      } 
     } 
     //}while(completed == false && (i < test.size())); 
     System.out.println("Prime numbers upto: " + maxNumber + ": " + test); 
    } 

    private static void removeMultiples(int primeToTest) { 
     ArrayList<Integer> temp = new ArrayList<>(); 
     for (Integer toTest : test) { 
      if (!(((toTest) % primeToTest) == 0)) { 
       temp.add(toTest); 
      } 
     } 
     test.clear(); 
     test.addAll(temp); 
    } 
}

由程序给出的输出的一个例子是如下：

What number would you like the prime numbers to be generated to? 
10 
Prime numbers upto: 10: [3, 5, 9]

显然，输出用于上述的例子应该是：

Prime numbers upto: 10: [2, 3, 5, 7]

来源

2015-07-01 James

尝试，因为它是在链路作出任何聪明的优化其实之前描述的实现算法。我没有看到你“标记”非素数，而是清除列表。只需首先在维基页面概览中实施四个步骤。这样调试会更容易。 – dpmcmlxxvi

您初始化test是[2,3,4,5...] ，将currentPrime设置为2（test[0]），删除此倍数（移除2）。我相信类似的事情发生在i获取要2 test[2] = 7

，因为你正在使用i通过test推动这不3和5发生，但也从test删除的项目，以便值i引用更改（因为该位置中的值已更改）。因此，在第一次通过while循环结束时，i已被提前至2，但未消除3或5的倍数（如果使用更大的maxNumber，则会看到该倍数）。

来源

2015-07-01 17:18:51

打我回答。我也建议简化你的条件陈述。现在你有！（（（toTest）％primeToTest）== 0）。这可以简化为toTest％primtToTest！= 0.可能会更容易阅读:)编辑：我只是注意到，这将删除您当前检查的数字，因为2％2 == 0，2永远不会被添加回在，所以我认为你可能需要调整，无论如何。 – Pherion

Eratosthenes算法的筛选表明，当您考虑一个素数currentPrime时，除了自身之外，您必须标记为非素数的所有倍数。在您的removeMultiples功能中，您也将移除currentPrime。

您在getPrimeList中重复的方式对我来说似乎也有点奇怪。我想你可能会摆脱completed变量和一些i >= test.size()测试。试着这么做：

import java.util.ArrayList; 
public class sieveOfEratosthenes { 
    private static final ArrayList<Integer> test = new ArrayList<>(); 
    public static void main (String [] args) { 
     java.util.Scanner tempInput = new java.util.Scanner(System.in); 
     System.out.println("What number would you like the prime numbers to be generated to?"); 
     int maxPrime = tempInput.nextInt(); 
     for(int i = 2; i <= maxPrime; i++) { 
      test.add(i); 
     } 
     getPrimeList(maxPrime); 
    } 

    private static void getPrimeList(int maxNumber) { 
     int sqrtOfNum = (int) Math.sqrt(maxNumber); 
     int temp = 0, i = 0, current_prime = 0; 
     //do { 
     while(current_prime <= sqrtOfNum && i < test.size()) { 
      current_prime = test.get(i);    
      removeMultiples(current_prime); 
      i++; 
     } 
     //}while(completed == false && (i < test.size())); 
     System.out.println("Prime numbers upto: " + maxNumber + ": " + test); 
    } 

    private static void removeMultiples(int primeToTest) { 
     ArrayList<Integer> temp = new ArrayList<>(); 
     tmp.add(primeToTest); 
     for (Integer toTest : test) { 
      if (toTest%primeToTest != 0) { 
       temp.add(toTest); 
      } 
     } 
     test.clear(); 
     test.addAll(temp); 
    } 
}

来源

2015-07-01 17:31:47 mziccard

为什么我的算法没有给出预期的输出？

回答

相关问题