소수

O(sqrt(n)) 시간 복잡도에서 빠르고 효율적인 방법으로 소수를 찾습니다.

소수를 효율적으로 검사하려면 주어진 숫자의 제곱근보다 작거나 같은 숫자로 나눌 수 없는 모든 숫자는 소수입니다.

먼저 입력 n을 받아 소수인지 여부를 확인합니다.
그런 다음 1보다 작거나 같은 숫자는 소수가 아니므로 유효한 숫자인지 여부를 확인합니다. 이 경우 함수는 -1을 반환합니다.

그런 다음 2 또는 3으로 나눌 수 있는지 확인하고 2 또는 3으로 나눌 수 있으면 0이 반환됩니다.

그런 다음 주어진 숫자의 제곱근 아래의 모든 숫자가 나눌 수 있는지 여부를 확인합니다.
더 효율적으로 확인하기 위해 변수 i를 5부터 시작하여 6씩 증가시키고 변수 i가 i와 i+2로 나눌 수 있는지 확인하고 이것이 0이면 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");
        }
    }
}