素数Java程序

Question

问题

在这个项目中，您将编写一个Java程序，该程序从标准输入中读取一个正整数n，然后打印出前n个素数。我们说，如果存在整数k使得m =
kd，则整数m可被非零整数d整除，即，如果d被均分为m。等效地，如果将m的整数除以d，则m可被d整除。我们也可以通过说d是m的除数来表达这一点。如果正整数p的唯一正数是1和p，则称其为质数。此规则的一个例外是数字1本身，它被视为非素数。非素数的正整数称为复合。欧几里得表明有无限多个质数。素数和复合序列如下所示：

Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …

Composites: 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, …

有很多方法可以测试数字的素数，但最简单的方法就是简单地进行除法运算。首先将m除以2，如果将其平均除，则m不是质数。否则，除以3，然后除以4，然后乘以5，以此类推。如果发现在任何一点处，m都可以被2
dm-1范围内的数字d整除，则停止，然后得出m是复合的结论。否则，得出m为质数的结论。片刻的想法表明，不必对本身是合成数字d进行任何除法运算。例如，如果试验除以2失败（即余数非零，所以m为奇数），则试验除以4、6或8或任何偶数也将失败。因此，要测试数字m的素数，只需用小于m的素数进行试除。此外，不必一直上升到m-1。只需在2
pm范围内对m除以质数p进行试验除法。为了看到这一点，假设m> 1是复合的。然后存在正整数a和b，使得1 <a m和b> m，则ab> m，与m = ab相矛盾。因此，a或b之一必须小于或等于m。

为了在Java中实现此过程，您将编写一个带有以下签名的函数isPrime（）：

static boolean isPrime(int m, int[] P)

该函数将根据m是质数还是复合数返回true或false。数组参数P将包含足够数量的质数以进行测试。具体来说，在调用isPrime（）时，数组P必须包含（至少）2
pm范围内的所有素数p。例如，要测试m = 53的素数，必须连续进行2、3、5和7的除法。自11>
53以来，我们不再赘述。因此，函数调用的前提是Prime（53，P）是P [0] = 2，P [1] = 3，P [2] = 5和P [3] =
7。由于所有这些除法都会失败，因此这种情况下的返回值将为true。与测试m = 143相似，必须进行2、3、5、7和11的除法运算（因为13>
143）。因此，函数调用的前提是Prime（143，P）为P [0] = 2，P [1] = 3，P [2] = 5，P [3] = 7和P [4] =
11。在这种情况下，返回值将为false，因为11除以143。函数isPrime（）应该包含一个循环，该循环逐步遍历数组P，进行尝试除法。当2尝试除法成功后，此循环应终止，在这种情况下将返回false，或者直到P中的下一个素数大于m为止，在这种情况下将返回true。该项目中的函数main（）将读取命令行参数n，分配一个长度为n的int数组，用质数填充该数组，然后根据下面描述的格式将数组的内容打印到stdout。在函数main（）的上下文中，我们将此数组称为Primes
[]。因此，数组Primes
[]在此项目中扮演双重角色。一方面，它用于收集，存储和打印输出数据。另一方面，它被传递给函数isPrime（）以测试新整数的素性。每当isPrime（）返回true时，新发现的素数将被放置在数组Primes
[]中的适当位置。该过程之所以有效，是因为如上所述，测试整数m范围至m所需的质数，并且在测试m时，所有这些质数（以及更多）都已经存储在数组Primes
[]中。当然，有必要手动初始化Primes [0] =
2，然后使用函数isPrime（）对素数进行测试3，4，…。测试m时，所有这些素数（以及更多素数）将已经存储在Primes
[]数组中。当然，有必要手动初始化Primes [0] =
2，然后使用函数isPrime（）对素数进行测试3，4，…。测试m时，所有这些素数（以及更多素数）将已经存储在Primes
[]数组中。当然，有必要手动初始化Primes [0] = 2，然后使用函数isPrime（）对素数进行测试3，4，…。

下面是函数main（）中要执行的步骤的概述。

• 检查用户是否正确提供了一个命令行参数，该参数可以解释为正整数n。如果命令行参数不是单个正整数，则程序将按照以下示例中的说明打印用法消息，然后退出。
• 分配长度为n的数组Primes []并初始化Primes [0] = 2。
• 输入一个循环，该循环将发现后续的素数并将其存储为Primes [1]，Primes [2]，Primes [3]，…，Primes [n -1]。该循环应包含一个内部循环，该循环遍历连续的整数，并通过使用适当的参数调用函数isPrime（）来测试它们的素性。
• 将Primes []数组的内容打印到stdout，将10打印到由单个空格分隔的行。换句话说，Primes [0]到Primes [9]将在第1行，Primes [10]尽管Primes [19]将在第2行，依此类推。请注意，如果n不是10的倍数，则输出的最后一行将包含少于10个素数。

您的程序（称为Prime.java）将产生与以下示例运行相同的输出。（通常，％表示Unix提示符。）

% java Prime 
Usage: java Prime [PositiveInteger] 
% java Prime xyz 
Usage: java Prime [PositiveInteger] 
% java Prime 10 20 
Usage: java Prime [PositiveInteger] 
% java Prime 75 
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 101 103 107 109 113 
127 131 137 139 149 151 157 163 167 173 
179 181 191 193 197 199 211 223 227 229 
233 239 241 251 257 263 269 271 277 281 
283 293 307 311 313 317 331 337 347 349 
353 359 367 373 379 
% 
3

如您所见，不合适的命令行参数会生成用法消息，该消息与许多unix命令的用法消息相似。（尝试执行不带参数的more命令以查看此类消息。）您的程序将包括一个具有签名的名为Usage（）的函数。

static void Usage()

将此消息打印到stderr，然后退出。因此，您的程序将总共包含三个函数：main（），isPrime（）和Usage（）。每个注释之前都应加一个注释块，给出其名称，其操作的简短描述以及任何必要的前提条件（例如isPrime（）的前提条件。）请参见网页上的示例。

尝试的解决方案

class Prime {
    public static void main(String[] args) {
        int num1 = 0;
        int num2 = 0;
        int num3;
        for (num1 = 1; num1 < 101; num1++)
            System.out.println(num1);
        for (num2 = 1; num2 < 101; num1++)
            System.out.println(num2);
        num3 = num2 % num1;
        if (num3 == 0)
            System.out.println("The prime numbers are " + num1);
        else
            System.out.println("The prime numbers are " + (num1 += 1));
    }
}

Answer 1

您的示例解决方案根本没有真正遵循问题的规范。您应该首先专注于编写static boolean isPrime(int m, int[] P)方法。该方法所需要做的就是：

• 迭代内容 P
• 如果一个元素均分m，m则为复合-返回false
• 如果元素的平方大于m，m则为质数-return true。从问题描述中听起来这永远不会发生，P只会有2到1的质数在越过sqrt(m)边界之前
• 如果的所有元素P均已测试，m则为素数-返回true

之后，您可以编写代码main来制作素数数组并使用所描述的循环对其进行构建，最后进行参数检查并实现该static void Usage()函数以在参数无效时调用