Prime测试，2位数字
我想打印所有2位数的素数。 这是我的代码：
for(int input = 11; input <= 99; input += 2){ for(int x = 2; x < (int)Math.sqrt(input) + 1; x++){ if(input%x != 0){ System.out.println(input); break; }else{ break; } } } 问题是它打印的数字如35或49不是素数。
这很有效。 你可以在这里看到输出。
public class Main { public static void main(String[] args) { for(int input = 11; input <= 99; input += 2){ boolean found = false; for(int x = 2; x < (int)Math.sqrt(input) + 1; x++){ if(input%x == 0){ found = true; break; } } if(!found) { System.out.println(input); } } } }
您对完整性的测试不正确。 一旦找到input不可被除数的除数，就停止测试数字（ input ）。
这不是素数的定义 – 你需要测试input数字不能被任何小于它的除数整除 – 换句话说，你需要在将数字声明为素数之前测试x所有值。
当input可以被x整除时，您可以突破检查input % x != 0的循环，但是当它不可分割时，则不能检查input % x != 0 – 当这个条件为真时你需要继续检查！
我总是喜欢这样一个问题：最简单和最明显的答案是硬编码输出：
System.out.println("11\n13\n17\n19\n23\n29\n31\n37\n41\n43" + "\n47\n53\n59\n61\n67\n71\n73\n79\n83\n89\n97");
要找到素数，你不需要测试它下面的每个数字，直到它的平方根; 你只需要测试它下面的每个其他素数。 这是一个演示：
ArrayList primes = new ArrayList (); // hold every other prime numbers that we find boolean isPrime; // add first base prime number primes.add(2); for (int x = 3; x < max; x+=2) { // start from 3 and skip multiples of 2 isPrime = true; // prove it's not prime for (Integer i : primes) { if (x % i == 0) { isPrime = false; // x is divisible by a prime number... break; // exit loop, we proved it's not a prime } } if (isPrime) { if (x >= 10) { System.out.println(x); // print only two digits prime numbers } primes.add(x); // add x to our prime our number list for future checks } }
** 编辑 **
静态方法中更灵活，可重用的实现（未针对列出大质数进行优化）：
public static List findPrimes(int min, int max) { LinkedList primes = new LinkedList (); boolean isPrime; double square; // add first base prime number primes.add(2); for (int x = 3; x < max; x+=2) { // start from 3 and skip multiples of 2 isPrime = true; // prove it's not prime square = Math.sqrt(x); for (Integer i : primes) { isPrime = x % i != 0; // x is not prime if it is divisible by i if (!isPrime || i > square) { break; } } if (isPrime) { primes.add(x); // add x to our prime numbers } } // remove all numbers below min while (!primes.isEmpty() && primes.getFirst() < min) { primes.removeFirst(); } return primes; }
方法用法：
List primes = findPrimes(10, 100); System.out.println("Listing " + primes.size() + " prime numbers"); for (Integer prime : primes) { System.out.println(prime); }
维基百科为查找素数提供了一个很好的算法。 它还列出了最多100个。
如果您正在寻找调试帮助，我只需单步执行您的代码，直到您看到哪些测试不正确。 这是一个快速简单的程序，不应该花很长时间。
问题出在这个块中：
if(input%x != 0) { System.out.println(input); break; }
如果它不能被’x’的当前值整除，它将打印’input’，但它可以被’x’的下一个值整除。 在这种情况下，“输入”不是素数，而是打印出来。
正确的代码：
boolean flag; for(int input = 11; input <= 99; input += 2) { flag = true; for(int x = 2; x < (int)Math.sqrt(input) + 1; x++) { if(input%x == 0) { flag = false; break; } } if(flag == true) System.out.println(input); }
您正在打印所有奇数。 你总是打破循环，所以x永远不会超过2。
if(input%x != 0){ System.out.println(input); break; // <<-- break here }else{ break; // <<-- and break here }
还要仔细考虑素数的定义：
- 如果您测试的任何数字都是精确的除数，则该数字不是素数。
- 如果您测试的所有数字都不是精确的除数，则数字为素数。
如果你发现了一个除数，你应该只打破循环。 如果你还没有找到一个，你需要继续前进，直到你测试了所有的可能性。 在你完成循环并知道结果之前，你不应该打印任何东西。
for(int input = 11; input <= 99; input += 2){ int found = 0; for(int x = 2; x < (int)Math.sqrt(input) + 1; x++) if(input%x == 0){ found = 1; break; } if(found == 0) System.out.println(input); }
这应该做的工作
是的，因为它打印出所有发现非因素的情况。 您只需要打印出无法找到因素的情况。