IT小君
2021-12-06T04:39:45 我正在为基本的 Java 考试练习过去的试卷，我发现很难让 for 循环工作来测试一个数字是否为素数。我不想通过为更大的数字添加效率措施来使它复杂化，只是一些至少适用于 2 位数字的东西。
目前，即使 n 是素数，它也总是返回 false。
我认为我的问题是我在 for 循环本身以及将“返回真”放在哪里时遇到了问题；和“返回错误；”......我确定这是我犯的一个非常基本的错误......
public boolean isPrime(int n) {
int i;
for (i = 2; i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
我无法在 stackoverflow 的其他地方找到帮助的原因是，类似的问题要求更复杂的实现以更有效的方式进行。
IT小君 您可以更早地停止并更快地跳过循环：
public boolean isPrime(long n) {
// fast even test.
if(n > 2 && (n & 1) == 0)
return false;
// only odd factors need to be tested up to n^0.5
for(int i = 3; i * i <= n; i += 2)
if (n % i == 0)
return false;
return true;
}
错误是 i<=n
for (i = 2; i<n; i++){
你应该写i < n，因为最后的迭代步骤会给你true。
IT小君 public class PrimeNumberCheck {
private static int maxNumberToCheck = 100;
public PrimeNumberCheck() {
}
public static void main(String[] args) {
PrimeNumberCheck primeNumberCheck = new PrimeNumberCheck();
for(int ii=0;ii < maxNumberToCheck; ii++) {
boolean isPrimeNumber = primeNumberCheck.isPrime(ii);
System.out.println(ii + " is " + (isPrimeNumber == true ? "prime." : "not prime."));
}
}
private boolean isPrime(int numberToCheck) {
boolean isPrime = true;
if(numberToCheck < 2) {
isPrime = false;
}
for(int ii=2;ii<numberToCheck;ii++) {
if(numberToCheck%ii == 0) {
isPrime = false;
break;
}
}
return isPrime;
}
}
用这个可被 3 整除的代码号将跳过 for 循环代码初始化。
For 循环迭代也将跳过 3 的倍数。
private static boolean isPrime(int n) {
if ((n > 2 && (n & 1) == 0) // check is it even
|| n <= 1 //check for -ve
|| (n > 3 && (n % 3 == 0))) { //check for 3 divisiable
return false;
}
int maxLookup = (int) Math.sqrt(n);
for (int i = 3; (i+2) <= maxLookup; i = i + 6) {
if (n % (i+2) == 0 || n % (i+4) == 0) {
return false;
}
}
return true;
}
您还可以在 for 循环中为此使用一些简单的 Math 属性。
数字“n”是质数当且仅当它可以被自身或 1 整除。如果一个数字不是质数，它将有两个因数：
n = a * b
您可以使用 for 循环来检查直到数字 'n' 的 sqrt，而不是一直到 'n'。如果'a' 和'b' 都大于数字'n' 的sqrt，a*b 将大于'n'。所以至少有一个因子必须小于或等于平方根。
所以你的循环将如下所示：
for(int i=2; i<=Math.sqrt(n); i++)
通过这样做，您将大大降低代码的运行时间复杂度。我认为它会归结为 O(n/2)。
IT小君 最快的方法之一是循环直到 n 的平方根。
private static boolean isPrime(int n){
int square = (int)Math.ceil((Math.sqrt(n)));//find the square root
HashSet<Integer> nos = new HashSet<>();
for(int i=1;i<=square;i++){
if(n%i==0){
if(n/i==i){
nos.add(i);
}else{
nos.add(i);
int rem = n/i;
nos.add(rem);
}
}
}
return nos.size()==2;//if contains 1 and n then prime
}
您正在检查.So 什么i<=n时候i==n，您只会得到 0 并且它总是返回 false。尝试。i<=(n/2)无需检查直到i<n。
IT小君 上面提到的算法将 1 视为素数，尽管它不是。因此，这是解决方案。
static boolean isPrime(int n) {
int perfect_modulo = 0;
boolean prime = false;
for ( int i = 1; i <= n; i++ ) {
if ( n % i == 0 ) {
perfect_modulo += 1;
}
}
if ( perfect_modulo == 2 ) {
prime = true;
}
return prime;
}
好吧，for 循环有一些问题。这是代码，
public static boolean checkPrimeNUmber(int number)
{
if(number <= 1)
{
return false;
}
for(int a = 2; a < Math.sqrt(number); a++)
{
if(number % a == 0)
{
return false;
}
}
return true;
}
用 Java 8 的方式做它更好更干净
private static boolean isPrimeA(final int number) {
return IntStream
.rangeClosed(2, number/2)
.noneMatch(i -> number%i == 0);
}
你的
for循环有点问题。它应该是： -for (i = 2; i < n; i++) // replace `i <= n` with `i < n`当然，您不想检查
n除以时的余数n。它总会给你的1。事实上，您甚至可以通过将条件更改为： - 来减少迭代次数
i <= n / 2。因为n不能被一个大于 的数整除n / 2，除非我们考虑n，我们根本不必考虑。因此，您可以将
for循环更改为：-for (i = 2; i <= n / 2; i++)