素数的 Java 程序

Java Program for Prime numbers

提问by Ben

Problem

问题

In this project you will write a Java program that reads a positive integer n from standard input, then prints out the first n prime numbers. We say that an integer m is divisible by a non-zero integer d if there exists an integer k such that m = k d , i.e. if d divides evenly into m. Equivalently, m is divisible by d if the remainder of m upon (integer) division by d is zero. We would also express this by saying that d is a divisor of m. A positive integer p is called prime if its only positive divisors are 1 and p. The one exception to this rule is the number 1 itself, which is considered to be non-prime. A positive integer that is not prime is called composite. Euclid showed that there are infinitely many prime numbers. The prime and composite sequences begin as follows:

在这个项目中，您将编写一个 Java 程序，该程序从标准输入中读取一个正整数 n，然后打印出前 n 个素数。我们说一个整数 m 可以被一个非零整数 d 整除，如果存在一个整数 k 使得 m = kd ，即如果 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, … 

There are many ways to test a number for primality, but perhaps the simplest is to simply do trial divisions. Begin by dividing m by 2, and if it divides evenly, then m is not prime. Otherwise, divide by 3, then 4, then 5, etc. If at any point m is found to be divisible by a number d in the range 2 d m?1, then halt, and conclude that m is composite. Otherwise, conclude that m is prime. A moment's thought shows that one need not do any trial divisions by numbers d which are themselves composite. For instance, if a trial division by 2 fails (i.e. has non-zero remainder, so m is odd), then a trial division by 4, 6, or 8, or any even number, must also fail. Thus to test a number m for primality, one need only do trial divisions by prime numbers less than m. Furthermore, it is not necessary to go all the way up to m?1. One need only do trial divisions of m by primes p in the range 2 p m . To see this, suppose m >1 is composite. Then there exist positive integers a and b such that 1 < a < m, 1 < b < m, and m = ab . But if both a > m and b > m , then ab > m, contradicting that m = ab . Hence one of a or b must be less than or equal to m .

有很多方法可以测试一个数的素性，但最简单的方法可能是简单地进行试除。首先将 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 范围内用素数 p 对 m 进行试除。为了看到这一点，假设 m >1 是复合的。那么存在正整数 a 和 b 使得 1 < a < m, 1 < b < m, and m = ab 。但如果 a > m 和 b > m ，则 ab > m，与 m = ab 矛盾。因此 a 或 b 之一必须小于或等于 m 。

To implement this process in java you will write a function called isPrime() with the following signature:

要在 Java 中实现此过程，您将编写一个名为 isPrime() 的函数，其签名如下：

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

This function will return true or false according to whether m is prime or composite. The array argument P will contain a sufficient number of primes to do the testing. Specifically, at the time isPrime() is called, array P must contain (at least) all primes p in the range 2 p m . For instance, to test m = 53 for primality, one must do successive trial divisions by 2, 3, 5, and 7. We go no further since 11 > 53 . Thus a precondition for the function call isPrime(53, P) is that P[0] = 2 , P[1] = 3 , P[2] = 5, and P[3] = 7 . The return value in this case would be true since all these divisions fail. Similarly to test m =143 , one must do trial divisions by 2, 3, 5, 7, and 11 (since 13 > 143 ). The precondition for the function call isPrime(143, P) is therefore P[0] = 2 , P[1] = 3 , P[2] = 5, P[3] = 7 , and P[4] =11. The return value in this case would be false since 11 divides 143. Function isPrime() should contain a loop that steps through array P, doing trial divisions. This loop should terminate when 2 either a trial division succeeds, in which case false is returned, or until the next prime in P is greater than m , in which case true is returned. Function main() in this project will read the command line argument n, allocate an int array of length n, fill the array with primes, then print the contents of the array to stdout according to the format described below. In the context of function main(), we will refer to this array as Primes[]. Thus array Primes[] plays a dual role in this project. On the one hand, it is used to collect, store, and print the output data. On the other hand, it is passed to function isPrime() to test new integers for primality. Whenever isPrime() returns true, the newly discovered prime will be placed at the appropriate position in array Primes[]. This process works since, as explained above, the primes needed to test an integer m range only up to m , and all of these primes (and more) will already be stored in array Primes[] when m is tested. Of course it will be necessary to initialize Primes[0] = 2 manually, then proceed to test 3, 4, … for primality using function isPrime().

该函数将根据 m 是素数还是合数返回真或假。数组参数 P 将包含足够数量的素数来进行测试。具体来说，在调用 isPrime() 时，数组 P 必须（至少）包含 2 pm 范围内的所有素数 p 。例如，要测试 m = 53 的素性，必须对 2、3、5 和 7 进行连续的试验除法。由于 11 > 53 ，我们不再进一步。因此，函数调用 isPrime(53, P) 的前提是 P[0] = 2 、 P[1] = 3 、 P[2] = 5 和 P[3] = 7 。在这种情况下，返回值将为真，因为所有这些划分都失败了。与测试 m =143 类似，必须对 2、3、5、7 和 11 进行试除（因为 13 > 143 ）。因此，函数调用 isPrime(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, ... 的素性。

The following is an outline of the steps to be performed in function main().

以下是要在函数 main() 中执行的步骤的概述。

• Check that the user supplied exactly one command line argument which can be interpreted as a positive integer n. If the command line argument is not a single positive integer, your program will print a usage message as specified in the examples below, then exit.
• Allocate array Primes[] of length n and initialize Primes[0] = 2 .
• Enter a loop which will discover subsequent primes and store them as Primes[1] , Primes[2], Primes[3] , ..., Primes[n ?1] . This loop should contain an inner loop which walks through successive integers and tests them for primality by calling function isPrime() with appropriate arguments.
• Print the contents of array Primes[] to stdout, 10 to a line separated by single spaces. In other words Primes[0] through Primes[9] will go on line 1, Primes[10] though Primes[19] will go on line 2, and so on. Note that if n is not a multiple of 10, then the last line of output will contain fewer than 10 primes.

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

Your program, which will be called Prime.java, will produce output identical to that of the sample runs below. (As usual % signifies the unix prompt.)

您的程序将被称为 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 

As you can see, inappropriate command line argument(s) generate a usage message which is similar to that of many unix commands. (Try doing the more command with no arguments to see such a message.) Your program will include a function called Usage() having signature

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

static void Usage() 

that prints this message to stderr, then exits. Thus your program will contain three functions in all: main(), isPrime(), and Usage(). Each should be preceded by a comment block giving it's name, a short description of it's operation, and any necessary preconditions (such as those for isPrime().) See examples on the webpage.

将此消息打印到 stderr，然后退出。因此，您的程序将包含三个函数：main()、isPrime() 和 Usage()。每个前面都应该有一个注释块，给出它的名称、操作的简短描述和任何必要的先决条件（例如 isPrime()。）请参阅网页上的示例。

Attempted Solution

尝试的解决方案

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

回答by Carl Manaster

Ben, it looks like you are attempting something that is far beyond your current capability. Start with some much simpler problems. Talk to your teacher and consider taking a more rudimentary course. You don't appear to understand either what the program is supposed to do, or how to write a program that might satisfy the requirements, and nothing we say here can overcome that - you have to develop more understanding of math and programming. We're happy to help with that, but just writing your program here won't help you, and you are too far away from a solution for suggestions to help. I'm sorry if this sounds harsh; honestly, I mean it constructively. Please stay with it - but start simpler.

本，看起来你正在尝试的东西远远超出你目前的能力。从一些更简单的问题开始。与您的老师交谈并考虑参加更基础的课程。您似乎既不了解程序应该做什么，也不了解如何编写可能满足要求的程序，我们在这里说的任何内容都无法克服这一点——您必须对数学和编程有更多的了解。我们很乐意为您提供帮助，但仅在此处编写您的程序对您没有帮助，而且您离解决方案太远了，无法提供帮助。如果这听起来很刺耳，我很抱歉；老实说，我的意思是建设性的。请坚持下去 - 但开始更简单。

回答by Michael Mrozek

Your example solution doesn't really follow the problem's specification at all. You should focus first on writing the static boolean isPrime(int m, int[] P)method. All that method needs to do is:

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

• Iterate over the contents of P
• If an element evenly divides m, mis composite -- return false
• If an element's square is greater than m, mis prime -- return true. It sounds like from the problem description this won't ever happen, Pwill only have the primes from 2 to the one just before crossing the sqrt(m)boundary
• If all the elements of Phave been tested, mis prime -- return true

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

After that you can write mainto make the primes array and build it up using the described loop, and finally do argument checking and implement the static void Usage()function to call if the arguments are invalid

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