0

问题

在这个项目中,您将编写一个 Java 程序,它从标准输入中读取一个正整数 n,然后打印出前 n 个素数。如果存在整数 k 使得 m = kd ,即如果 d 均分到 m,我们说整数 m 可被非零整数 d 整除。等效地,如果 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 进行任何尝试除法,数字 d 本身是复合的。例如,如果试除以 2 失败(即余数非零,因此 m 是奇数),则试除以 4、6 或 8 或任何偶数也必须失败。因此,要测试一个数 m 的素数,只需用小于 m 的素数进行试除即可。此外,没有必要一直到 m-1。只需在 2 pm 范围内将 m 除以素数 p 即可。为了看到这一点,假设 m >1 是复合的。那么存在正整数 a 和 b 使得 1 < a < m,1 < b < m,并且 m = ab 。但如果 a > m 和 b > m 都存在,则 ab > m,与 m = ab 相矛盾。因此 a 或 b 之一必须小于或等于 m 。

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

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

此函数将根据 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 。在这种情况下,返回值将是 true,因为所有这些划分都失败了。与测试 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。在这种情况下,返回值将是假的,因为 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[] 的内容打印到标准输出,将 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));
    }
}
4

2 回答 2

5

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

于 2010-05-14T01:47:36.397 回答
3

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

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

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

于 2010-05-14T01:38:20.983 回答