为什么我不能在这个计算从 0 到 n 的所有素数的程序中输入大值 (e.x.n = 100000)？

Question

我对编码还很陌生，我这学期才开始学习 Java。我在四处乱逛并创建了这个 java 程序，它可以找到从 0 到 n 的所有素数。它使用模数和嵌套 for 循环并将其输出到数组列表中。现在，我用 n = 5、n = 100、n = 1000 和 n = 10000 测试它，它工作得很好，并给了我准确的结果，但是当我输入 n = 100000 时，控制台只是空白，没有给我任何信息完全输出。我意识到，对于大量的数字，它会花费更长的时间，所以我期待着等待它对所有的数字进行处理，但它只是“放弃了”。

这是计算超时的结果吗？是否有一个覆盖，所以我可以用更大的数字来计算这个？我意识到这不是最有效的代码（即 for 循环中的计算可能会执行两次）但这不是这里的问题所在。问题是为什么一定数量停止输出，有没有办法绕过这个。

我把我的代码放在下面，分成两个块，因为我有两个不同的类。

谢谢:)

General.java


import java.util.ArrayList;
import java.util.Scanner;

public class General 
{
    
    
    

    public static void main(String[] args) 
    {
        Scanner number = new Scanner(System.in);
        
        ArrayList<Integer> result = new ArrayList<Integer>();
        
        System.out.print("What is the number you want to find all the primes that are smaller than it: ");
        long n = number.nextInt();
        
        PrimeNumberSeeker pNS = new PrimeNumberSeeker();
        
        result = pNS.PrimesFromZero(n);
        
        for (int m = 0; m < result.size(); m++)
                {
                System.out.print(result.get(m));
                
                if (m+1 >= (result.size()))
                    System.out.print(".");
                else 
                    System.out.print(", ");
                }

    }

}

PrimeNumberSeeker.java


import java.util.ArrayList;


public class PrimeNumberSeeker 
{
    ArrayList<Integer> primes = new ArrayList<Integer>();

    
    public ArrayList<Integer> PrimesFromZero(long n)
    {
        for (int i = 0; i <= n; i++) //selects all numbers from 0 - n inclusive
        {
            int check = 0;
            //System.out.println(i);
            for (int j = 1; j <= i; j++) //we make sure not to include 1 and itself (n)
            {
                
                
                    if (i % j == 0)
                    check += 1;
                
                
                
                //System.out.println(i + " " + j);
            }
            if (check == 2)
                primes.add(i);
                
        }
        
        return primes;
    }
    
}

Answer 1

这只是一个计算复杂度的问题，你的算法可以在不同方面进行优化以降低其复杂度：

您不需要 check 变量
您可以将 j 范围限制在 2 到 sqrt(i)
如果 i%j==0 你可以停止对 i 的调查：它不是素数

其他建议：

总是使用括号
函数名称使用 lowerCamelCase
不要混用 int 和 long，为了您的目的 int 就足够了

此算法不是最好的，但适用于高达 10.000.000（或更多）的数字：

class PrimeNumberSeeker {
    public ArrayList<Integer> primesFromZero(int n) {
        ArrayList<Integer> primes = new ArrayList<Integer>();
        
        for (int i = 1; i <= n; i++) {
            boolean isPrime = true; // say your number is prime (we'll verify)
            for (int j = 2; j <= Math.sqrt(i); j++) { // verify if it really is
                if (i % j == 0) {
                    isPrime = false; // it isn't
                    break; // no more checks are needed, go out from this for cycle
                }
            }
            
            if (isPrime) { // if isPrime is still true then i is prime
                primes.add(i);
            }
        }
        
        return primes;
    }
}

Answer 2

您的程序是运行。我刚刚测试了它。您可以通过立即打印每个找到的素数来可视化进度：

        if (check == 2) {
            primes.add(i);
            System.out.println(i);
        }

你还可以看到，数字越大，进度越慢。那是因为你的 rumtime complexity 是 O(n^2)（平方）。对于每个数字，您测试每个较低的数字。这意味着如果你从 n=10.000 到 n=100.000 你的程序需要的时间远远超过 10 倍。

对于质数计算，请查看算法 Sieve of Eratosthenes。这在计算时间方面效率更高。

为什么我不能在这个计算从 0 到 n 的所有素数的程序中输入大值 (e.x.n = 100000)？

Why can I not enter large values (e.x. n = 100000) in this program that calculates all prime numbers from 0 to n inclusive?

java

primes

for-loop