LeetCode--所有质数、质数对

1.0 Q: 输出 100 以内所有质数

1.1

/* 第一层循环控制检查到哪个数* 第二层通过遍历除以每个比他小的数的方式,检查每个数是不是质数* 由于要遍历检查,设置一个标记,只要任意一次循环可以整除,我们就设置该标记为不是质数
*/boolean isPrime = true;for (int i = 2; i <= 100; i++) {for (int j = 2; j < i; j++) {if ( i % j == 0 )isPrime = false;}if(isPrime == true)System.out.println();

存在的问题

• 第二层循环中 j < i 次数太多了
  例如，检查 20 是不是质数。用 20 除 1/2/3/…，但是，除到 10 就可以停止了，因为用 20 除 11/12是没有意义的，是一定不能整除的，不影响质数判断。
• 在每次外层循环开始时，将 isPrime 重置为 true，确保对每个数字i的新检查都是从假设它是质数开始的。在错误的版本中，由于没有刷新这个状态，导致从第一个不是质数的数开始，就一直是 false 到结束了。
• 添加 break 语句，在发现非质数时立即退出内层循环，避免不必要的迭代。

1.2

boolean isPrime = true; for (int i = 2; i <= 100; i++) {isPrime = true; // 每次检查新数时，需要重置isPrime为true//除到自己的一半大的数就可以停止,继续是没有意义的.for (int j = 2; j < i/2; j++) {if (i % j == 0) { isPrime = false; break; // 一旦确定不是质数，就跳出循环，提高效率}}if (isPrime) { System.out.println(i); }
}

2. 找 100 以内两两相邻的、且差值于2的质数对

例如 (3，5）（5，7）（11，13）

• 思路 1 ：先找出所有质数，顺序装入数组。用 for 循环遍历，只要 prime[i]+ 2 == primes[i+1]，就输出这两个数
• 思路 2：每次找出一个质数 i，就直接判断 i + 2 是不是质数，如果也是，那就输出这两个数

这里实现思路 2.

• 相对与第一题，这里还有一个改进。那就是提前用 num = i 接住最外层的循环值（检查到哪个数了）

    for (int i = 2; i <= 100; i++) {boolean isPrime = true;for (int j = 2; j < i / 2; j++) {if (i % j == 0) {isPrime = false;}}if (isPrime) {i += 2;boolean isPrime2 = true;for (int k = 2; k <= i / 2; k++) {if (i % k == 0) {isPrime2 = false;}}if (isPrime2)System.out.println(i + "," + (i - 2));}}

对于输出结果来说，显然不对，（3，5）被忽略了。

分析：

可以看到，第一轮检查 2 时，是正常的。即检查 2 是质数后，将 i + 2，检查 4 不是质数， 所以不输出。接下来应当检查 3 。
但是，由于 i + 2 这个操作仍是在最外层循环内做的，因此这个操作会将这个改变带到下一次的大循环，直接来说就是下一次不检查 3 了，变成检查 5 了

    for (int i = 2; i <= 100; i++) {//要使用且改变外层循环的层数,预先定义一个变量来接收,这样就不会影响到外层循环int num = i;boolean isPrime = true;for (int j = 2; j < num / 2; j++) {if (num % j == 0) {isPrime = false;}}if (isPrime) {num += 2;boolean isPrime2 = true;for (int k = 2; k <= num / 2; k++) {if (num % k == 0) {isPrime2 = false;}}if (isPrime2)System.out.println(num + "," + (num - 2));}}