Prime数字的Java程序 [英] Java Program for Prime numbers

问题描述

在这个项目中，你将编写一个从标准输入读取正整数n的Java程序，然后
打印出前n个素数。我们说如果
存在整数k使得m = k d，即如果d均匀地划分为m，则整数m可被非零整数d整除。等价地，如果
除以m（整数）除以d的余数为零，则m可被d整除。我们也会通过说d是m的
除数来表达这一点。如果正整数p的唯一正除数为1且p为正整数p，则称为素数。此规则的一个
例外是数字1本身，它被认为是非素数。
不是素数的正整数称为复合。欧几里德表明，有无数的素数。素数
和复合序列的开头如下：

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:

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 p m范围内的素数p进行m的试验分割。为了看到这一点，假设m> 1是复合的。
然后存在正整数a和b，使得1< a< m，1< b< m，m = ab。但如果
a> m且b> m，则ab> m，与m = ab相矛盾。因此，a或b中的一个必须小于
或等于m。

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 .

要在java中实现这个过程，你将使用以下
签名编写一个名为isPrime（）的函数：

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

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

此函数将根据m是素数还是复合函数返回true或false。数组
参数P将包含足够数量的素数来进行测试。具体来说，在调用
isPrime（）时，数组P必须包含（至少）2 p m范围内的所有素数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以来）。函数调用的
前提条件是Preme（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是$ b时，所有这些素数（以及更多）将已经存储在数组Primes []中。 $ b测试。当然有必要手动初始化Primes [0] = 2，然后使用函数isPrime（）继续测试3,4，...
的primality。

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().

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

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

• 检查用户是否提供了一个命令行参数，该参数可以解释为
  正整数n。如果命令行参数不是单个正整数，则程序
  将打印下面示例中指定的用法消息，然后退出。


• 分配长度为n的数组Primes []并初始化Primes [0] = 2。


• 输入一个循环，它将发现后续素数并将它们存储为Primes [1]，Primes [2]，
  Primes [3]，...，Primes [n - 1]。这个循环应该包含一个内部循环，它遍历
  连续的整数，并通过使用适当的
  参数调用函数isPrime（）来测试它们的primality。


• 将数组Primes []的内容打印到stdout，10到由单个空格分隔的行。在其他
  单词中，Primes [0]到Primes [9]将会出现在第1行，Primes [10]，虽然Primes [19]将在第2行出现
  ，依此类推。请注意，如果n不是10的倍数，那么最后一行输出将包含
  少于10个素数。

• 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.

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

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.)

% 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 

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

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

static void Usage() 

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

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.

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

推荐答案

您的示例解决方案根本不符合问题的规范。您应该首先关注编写静态布尔值isPrime（int m，int [] P）方法。所有这些方法需要做的是：

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:

• 迭代 P <的内容/ li>
  
• 如果元素均分 m ， m 是复合的 - 返回 false


• 如果元素的平方大于 m ， m 是素数 - 返回 true 。这听起来像问题描述中不会发生这种情况， P 只有在穿越 sqrt之前才有从2到1的素数（ m） boundary


• 如果测试了 P 的所有元素， m 是素数 - 返回 true

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

之后你可以编写 main 来制作primes数组并使用描述的循环构建它，最后进行参数检查并实现 static void Usage （）如果参数无效，则调用函数

After that you can write main to 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

这篇关于Prime数字的Java程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！