3

我在编写一个查找 2-50 之间的素数的程序时遇到了麻烦。我的程序现在找到“大部分”素数，但包括一些非素数。我知道有很多更有效的方法和策略可以找到素数，但在我转向更有效和更有效的策略之前，我会先尝试所有可能性。现在编写程序的方式，如果它确实找到了一个素数，它会打印多次，而我只希望它打印一次。我的程序在概念上是正确的还是我的理由有缺陷。为什么我的程序主要找到素数但抛出一些非素数？为什么我的程序会多次打印素数？

这是我解决问题的方法。

  1. 创建一个 for 循环来表示 2-50 之间的潜在质数。用变量“i”表示这些潜在的素数。这个循环将从 50 开始倒计时。

  2. 由于一个数字只有在除了它自己和 1 之外没有其他可整除的数字时才是素数，我想创建一个内部 for 循环来将 i 除以 2 和 i -1 之间的每个可能数字，以查看这些数字中的任何一个是否均分到 i . 用变量 j 表示这些可能的除数。如果在任何时候 j 确实均匀地划分为 i 它不是质数，所以我希望我的内部循环退出。

  3. 如果 i 除以 j 的所有数字并且没有数字均匀地除以 i 则该数字如果是素数并且想要打印该数字。

*

import acm.program.*;
public class PrimeNumber extends ConsoleProgram{
public void run(){

  for (int i =50; i >= 2; i--){
    for (int j= 2; j < i-1; j++){

        if (i % j >= 1){
         println(i);
         }else{
         if (i % j == 0) break;
                }
              } /*end of inner loop */  
           } /* end of for loop */

       } /* end of run method */
     }
4

7 回答 7

2

你犯了2个错误。第一个在@Thomas 的评论中解释，第二个在@rolfl的评论中解释。我在这里更正了它们：

public class PrimeNumber extends ConsoleProgram {
    public void run() {
        for (int i = 50; i >= 2; i--) {
            boolean isPrime = true;
            for (int j = 2; j < i-1; j++) { //increment "j" not "i"
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) System.out.println(i);
        }
    } 
}

注意：我使用此代码验证了解决方案（在您的 IDE 中保存为 PrimeNumber.java）：

public class PrimeNumber {
    public static void main (String args[]) {
        for (int i = 50; i >= 2; i--) {
            boolean isPrime = true;
            for (int j = 2; j < i-1; j++) { //increment "j" not "i"
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) System.out.println(i);
        }
    } 
}

编辑：为了您的理解，您的主要问题是这里的逻辑：

for (int j= 2; j < i-1; j++) {
    if (i % j >= 1) {
        println(i);

您i只检查了一种可能性后进行打印。

例如，采取i = 7. 您必须先测试= i % j6、5、4、3j和 2，然后才能说它i是素数。你不能像你所做i % j的那样只测试 。j = 6为此，您的println语句应位于 for 循环之后，而不是嵌套在其中，因此您可以测试jfirst 的所有可能值。

编辑2：响应

巧合的是，作业的第一部分是编写一个谓词方法，如果数字是素数，则返回 true，如果不是素数，则使用蛮力策略返回 false。作业的第二部分是找到一种更有效的方法，并将作业的第一部分重新工作以提高效率。我试图用两个 for 循环来解决这个问题，看看我能不能做到。可以只用两个不带标签的 for 循环来完成并继续，因为我的书还没有涉及吗？

尝试这样的事情：

public boolean isPrime(int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0) {
            return false; //not prime
        }
    }
    return true; //prime
}
于 2013-05-24T02:33:59.937 回答
1

你正确地观察到，如果一个数i可以被一个数整除j，那么i % j == 0。

但是，每次您发现 i 的情况时，您都会打印i % j >= 0- 这并不意味着它i是素数，因为可能还有其他j一些i可以被平均划分的情况。

相反，您应该首先检查所有的j，并且只有当它们都没有给您== 0时，您才应该考虑i素数。您可以使用isPrime最初为 的布尔变量true，但内部 for 循环false一旦找到可以被均分的 a 就会j设置i为。

于 2013-05-24T02:01:43.190 回答
1

您的第二个循环（内部循环）中有一个错误。

你应该增加j而不是i......即内循环应该是

for (int j= 2; j < i-1; j++){

并不是

for (int j= 2; j < i-1; i++){
于 2013-05-24T02:03:15.870 回答
0

您的代码有 3 个问题：

  • 在内部循环中，您正在增加i而不是增加j.

  • 您尽快打印数字i % j >= 1，但也许下一个j会除以i，因此i不是素数。

  • 您应该在 sqrt(i) 处停止内部循环以避免无用的测试。

这是代码的更正版本：

OUTER: for (int i = 50; i >= 2; i--) {
    for (int j = 2; j <= (int) Math.sqrt(i); j++) {
        if (i % j == 0)
            continue OUTER;
        } /* end of inner loop */
    println(i);
} /* end of for loop */
于 2013-05-24T02:33:58.580 回答
0

这个 if 语句：

if (i % j >= 1){
         println(i);

将打印每个未除以 j 数字的数字，并且您要打印的数字不是那些从一个减法中获得不同于 0 的除法值的数字，而是对于所有减法。

此外，更快的解决方案是采用潜在素数的布尔数组并像这样循环。

for ( i = 2; i < sqrt(maxvalue); i ++){
            for(j = 1; j < sqrt(maxval); j++){
                  potentialy_prime[i*j]=false
            }
       }
for (potentialy_prime){
    if(potentialy_prime[i]==true)
            print(i "is prime")
}
于 2013-05-24T02:07:28.423 回答
0

查看 dydx 对这个问题的回答：https ://stackoverflow.com/questions/13437162/java-finding-prime-numbers 。或者这个问题：素数计算乐趣或这个获取素数等......

于 2013-05-24T02:08:11.803 回答
0

此代码应打印出质数。最初的假设是每个整数 >= 2 都是素数（在布尔数组中为真）。在遍历数组时，如果发现该数字是素数，则通过在布尔数组中将它们设置为 false 来删除该数字的倍数（因为它们不是素数）。最后，布尔数组中为真的数字将仅是素数。

时间复杂度：O(n log(log n))

public class PrimesImprovement
{
    public static void main(String[] args)
    {  
        System.out.println("Printing primes from 1 to 100");
        int i;
        int j;
        //boolean prime;
        boolean[] prime_arr=new boolean[100];
        Arrays.fill(prime_arr,true); // Assumption
        prime_arr[0]=prime_arr[1]=false;  // As 0 and 1 are not prime numbers
        for ( i=2;i<prime_arr.length;i++) 
        {

            if(prime_arr[i])
            { 
                for ( j=2;i*j<prime_arr.length;j++) 
                {
                    prime_arr[i*j]=false;
                }
            }
        }

        for( i=0; i<prime_arr.length; i++)
        {
            if(prime_arr[i])
            {
                System.out.print(i+" ");
            }
        }

        System.out.println();
    }
}
于 2015-07-27T13:11:39.190 回答