在 Java 中查找素数

Question

我遇到了一个 Java 程序，它可以查找给定的数字是否是素数。 这是代码。

class FindPrime {
    public static void main(String args[]) {
        int num;
        boolean isPrime;
        num = 14;

        if (num < 2) 
          isPrime = false;
        else 
          isPrime = true;

        for (int i = 2; i <= num / i; i++) {
            if ((num % i) == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) 
          System.out.println("Prime");
        else 
          System.out.println("Not Prime");
    }
}

在这里，我不确定为什么我会出现这种情况<= num/i is used in the for loop. Can someone please explain me?

Answer 1

限制条件

i <= num / i

是性能优化：

给定例如

num = 11

和

i = 3

，到目前为止，我们已经检查了11是否可以被2除（否），现在正在移动到3，我们应该检查它，答案是否定的，它不能被3整除。现在我们正在移动到4，我们还应该检查11是否能被它整除吗？这样的除法将得到 2.75，这个值小于我们已经检查过的 3。任何更高的

i

都会产生更小的值，我们已经检查过所有这些值，因此没有必要进一步检查。我们现在知道答案了。

Answer 2

不要忘记，像for(A;B;C)

这样的

for循环，表达式A在循环开始时计算一次，表达式B从第一个循环开始计算，表达式C从第二个循环开始计算.

所以最好将偏差从B部分移至A部分。

i < num / i是性能优化，而且检查第一个

Math.sqrt(num)

元素就足够了。

public static boolean isPrime(int val) {
    if (val < 2)
        return false;

    for (int i = 2, max = (int)Math.sqrt(val); i <= max; i++)
        if (val % i == 0)
            return false;

    return true;
}

Answer 3

i <= num/i

就像在做

i <= sqrt(num)

。
如果 num 不是素数，我们可以将它分解为

num = a * b

。
如果 num 的一个因子大于 num 的平方根，则另一个 必须 小于 num 的平方根。
如果两者都大于它，那么它的乘积将大于 num。

Answer 4

这是检查素数与否的更好方法

package com.practice.competitive.maths;

import java.util.Scanner;

public class CheckPrime {

    public static void main(String[] args) {

        try(Scanner scanner = new Scanner(System.in)) {
            int testCases = scanner.nextInt();
            long number = scanner.nextLong();
            String result = compute(number);
            System.out.println(result);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static String compute(long number) {
        if(number > 0 &&  number % 2 == 0)
            return "No";
        long sqrt = floorSqrt(number);
        for(long i = 3; i<sqrt;i+=2) {
            if(number % i == 0)
                return "No";
        }
        return "Yes";
    }

    private static long floorSqrt(long number) {
        if(number == 0 || number == 1)
            return number;
        long start = 0;
        long end = number;
        long answer = 0;
        while (start <= end) {
            long mid = (start + end)/2;
            if(mid*mid == number)
                return mid;
            if(mid*mid < number) {
                start = mid+1;
                answer = mid;
            }else {
                end = mid-1;
            }
        }
        return answer;
    }

}

Answer 5

下面的解决方案使用 Sieve of Sundaram 打印出用户提供的数字之前的所有质数：

请注意，对于大输入，您可能会遇到 OutOfMemoryError。

public static void isPrime(int num) {
    int k = (num - 2) / 2;
    int[] a = new int[k + 1];
    for (int i = 1; i < k + 1; i++) {
        int j = i;
        while ((i + j + 2 * i * j) <= k) {
            a[i + j + 2 * i * j] = 1;
            j += 1;
        }
    }
    if (num > 2) {
        System.out.println(2);
    }

    for (int l = 1; l < k + 1; l++) {
        if (a[l] == 0) {
            System.out.println((2 * l + 1));
        }
    }
}

Answer 6

在程序中添加 for 循环是不明智的，因为它们给你的时间复杂度大于 O(n) 线性时间复杂度，但 if 语句是明智的，这里有一个例子

// code contributed by akoyama koke

public class prime
{
    public static void main(String[] args) 
    {
        int []arry={1,23,71,3,4,5,6,8,21};
        int n=arry[8];
        if(n%2==0)
        {
            System.out.print("number is even:"+" "+n);
        }
        else if(n%2!=0)
        {
            if(n%3!=0 && n%5!=0 && n%7!=0)
            {
                 System.out.print("number is prime:"+" "+n);
            }
            else
            {
                System.out.print("number is odd and not prime:"+"  "+n);
            }
        }
        else
         System.out.println("number either decimal or a negative not catared for:"+" "+n);
    }
}    

Answer 7

这里是在素数中使用数组的java程序

import java.util.Scanner;
public class PrimeNo_array
{
    public static void main(String args[])
    {
       Scanner sc=new Scanner(System.in);
       int number;
       int factorCount=0;
       System.out.println("Enter a no");
       number=sc.nextInt();
       int[] factors = new int[number];
       for(int i=1;i<=number;i++)
       {
           if(number % i==0)
           {
               factors[factorCount]=i;
               factorCount++;
            }
        }
        if(factorCount==2)
        {
            System.out.println(number + "is a prime number");
        }
        
        else
        {
            System.out.println(number + "is not a prime number");
            System.out.print("Factors: "+factors);
            for(int i=0;i<factorCount;i++)
            {
                System.out.println(factors[i]+" ");
            }
        }
    }
}

Answer 8

是的。 for 循环的中间部分始终会被求值，并且仅当求值给出真值时循环内容才会运行。 在你的情况下，循环将在第一个周期停止，因为 14/2 的模数为 0，因此它将运行 if 主体，将布尔值设置为 false 并退出循环。