Нахождение простого числа в 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");
    }
}

Здесь я не уверен, почему условие i <= num / i используется в цикле for. Может кто-нибудь, пожалуйста, объясните мне? </p>

Answer 1

Это лучший способ проверить простое число или нет

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 2

i <= num/i это похоже на i <= sqrt(num).
Если num не простое число, мы можем разложить его на num = a * b.
Если коэффициент num больше квадратного корня из num,другой должен быть меньше квадратного корня из num.
Если бы оба были больше его, то его произведение было бы больше, чем num.

Answer 3

Ограничивающим условием i <= num / i является оптимизация производительности:

Учитывая, например, num = 11 и i = 3, мы до сих пор проверяли, можно ли разделить 11 на 2 (нет), и теперь переходим к3, и мы должны это проверить, ответ - нет, он не может быть разделен на 3. Теперь мы переходим к 4, должны ли мы все еще проверять, можно ли разделить 11 на это?Такое деление даст 2.75, значение меньше 3, которое мы уже проверили.Любое большее значение i даст еще меньшие значения, все из которых мы уже проверили, поэтому нет смысла проверять дальше.Мы уже знаем ответ.

Answer 4

Не забывайте, что для цикла типа for(A;B;C) выражение A вычисляется один раз в начале цикла, выражение B вычисляется для каждого цикланачиная с первого, вычисляется выражение C , начинающееся со второго цикла.

Так что лучше переместить отклонение от секции B к секции A .

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 5

да, это так.Средняя часть цикла for всегда оценивается, и содержимое цикла выполняется только в том случае, если оценка дает истинное значение.В вашем случае цикл остановится в своем первом цикле, так как модуль 14/2 равен 0, поэтому он запустит тело if, которое установит логическое значение равным false, и выйдет из цикла.