Простые числа

Чтобы найти простые числа быстрым и эффективным способом за O (sqrt (n)) временной сложности.

Для эффективной проверки простых чисел любое число является простым числом, если оно не делится ни на одно число, меньшее или равное квадратному корню из данного числа.

Сначала мы берем входное значение n, чтобы проверить, является ли оно простым или нет. затем число проверяется, является ли оно допустимым числом или нет, поскольку числа, меньшие или равные 1, в этом случае не являются простыми наша функция prime возвращает значение -1 .

Затем проверяется делимость на 2 или 3, если она делится на 2 или 3, то возвращается 0.

Затем мы проверяем все числа ниже квадратного корня из данного числа, делится ли оно или нет. Чтобы проверить это более эффективно, мы повторяем переменную i начиная с 5 и увеличьте его на 6 и мы проверяем, что оно делится на i и i+2 если это так, то возвращается 0, иначе данное число является простым числом.

Эта программа проверяет наличие простых чисел во временной сложности o(sqrt(n)).

import java.util.*;
public class Prime {
    static int prime(int n){
        if(n<=1){
            return -1;
        }
        if(n==2||n==3){
            return 1;
        }
        if(n%2==0||n%3==0){
            return 0;
        }
        for(int i=5;i*i<=n;i=i+6){
            if(n%i==0||n%(i+2)==0){
                return 0;
            }
        }
        return 1;
    }
    public static void main(String args[]) {
        Scanner sc=new Scanner(System.in);
        int n,r ;
        System.out.println("Enter the number to check");
        n=sc.nextInt();
        r=prime(n);
        System.out.println(r);
        if(r==-1){
        System.out.println("Please enter a valid number");
        }
        else if(r==0){
            System.out.println(""+n+" is not a prime number");
        }
        else{
            System.out.println("It is a prime number");
        }
    }
}

Оригинал: “https://dev.to/221910304057vivek/prime-numbers-569h”