Java 소수 판별 프로그램 (예제 포함)

소수란 무엇입니까?

소수란 1보다 큰 자연수 중에서 1 또는 자기 자신으로만 나누어지는 수를 말합니다. 예를 들어, 11은 1 또는 자기 자신으로만 나누어집니다. 다른 소수로는 2, 3, 5, 7, 11, 13, 17 등이 있으며, 이 수열은 끝없이 이어집니다.

1보다 크고 소수가 아닌 수를 합성수라고 합니다. 합성수는 자신보다 작은 약수로 나눌 수 있기 때문입니다. 9는 3으로 나누어 떨어지므로 합성수이고, 15는 3과 ​​5로 나누어 떨어지므로 합성수입니다.

참고 : 0과 1은 소수가 아닙니다. 2는 유일한 짝수 소수이며, 음수는 절대 소수로 간주되지 않습니다.

어떤 숫자가 소수인지 확인하는 방법 Java

검증 전략은 간단한 나눗셈 테스트입니다. 후보 값을 가져와서 각각 더 작은 정수로 차례로 나누고 나머지를 확인합니다. 나머지가 0이면 약수가 존재함을 증명하는 것이므로 해당 숫자는 즉시 부적합합니다.

프로그램 논리:

• 주어진 숫자(예: 17)를 2부터 17까지의 값으로 나누고 나머지를 확인해야 합니다. 나머지가 0이면 그 숫자는 소수가 아닙니다.
• 어떤 숫자도 자신의 절반 이상으로 나누어지지 않습니다. 그래서 우리는 고리 그냥 통해 numberToCheck/2입력값이 17이면 절반은 8.5이고, 반복문은 2부터 8까지의 값을 순회합니다.
• numberToCheck가 다른 수로 완전히 나누어떨어지면 isPrime 플래그가 설정됩니다. false 루프가 종료됩니다.

두 Java 특징들이 전체 알고리즘을 구성합니다. 모듈러스 연산자 % 정수 나눗셈의 나머지를 반환합니다. break 해당 구문은 답을 알게 되는 즉시 루프를 중지하므로 불필요한 반복이 실행되지 않습니다.

Java 숫자가 소수인지 아닌지 확인하는 프로그램

아래 프로그램은 numberToCheck 변수에 17이라는 값을 할당하고 나눗셈 과정을 단계별로 출력하여 계산 과정을 따라갈 수 있도록 합니다. 코드는 수정 가능하므로, 값을 변경하고 21과 같은 합성수를 넣어 다시 실행하면 반대 결과가 나오는 것을 확인할 수 있습니다.

public class PrimenumberToCheckCheck {

 public static void main(String[] args) {
  int remainder;
  boolean isPrime=true;
  int numberToCheck=17; // Enter the number you want to check for prime

  //Loop to check whether the number is divisible by any number other than 1 and itself
  for(int i=2;i<=numberToCheck/2;i++)
  {
   //number is divided by i
            remainder=numberToCheck%i;
            System.out.println(numberToCheck+" Divided by "+ i + " gives a remainder "+remainder);

       //if remainder is 0 then the number is not prime and we break the loop. Else continue the loop
     if(remainder==0)
     {
        isPrime=false;
        break;
     }
  }
  // Check value true or false, if isPrime is true then the number is prime otherwise not prime
  if(isPrime)
     System.out.println(numberToCheck + " is a Prime number");
  else
     System.out.println(numberToCheck + " is not a Prime number");
    }
  }

예상 출력 :

17 Divided by 2 gives a remainder 1
17 Divided by 3 gives a remainder 2
17 Divided by 4 gives a remainder 1
17 Divided by 5 gives a remainder 2
17 Divided by 6 gives a remainder 5
17 Divided by 7 gives a remainder 3
17 Divided by 8 gives a remainder 1
17 is a Prime number

17을 2로 나누면 정수 연산에서 8이 되므로 루프는 8에서 멈춥니다. 나머지가 0이 될 수 없으므로 isPrime 플래그는 초기값인 true를 유지하고 최종 조건은 긍정적인 결과를 출력합니다.

제곱근 방법을 이용한 최적화된 소수 판별

수의 절반까지 나누는 것은 맞지만 비효율적입니다. 어떤 수 n의 약수가 제곱근보다 크다면, 그에 상응하는 공동 약수는 제곱근보다 작아야 하므로 이미 발견되었을 것입니다. 따라서 √n까지 확인하는 것이 훨씬 적은 반복 횟수로 동일한 답을 얻을 수 있습니다.

public class PrimeCheckOptimized {

    public static boolean isPrime(int n) {
        // 0, 1 and negative values are never prime
        if (n <= 1) {
            return false;
        }
        // 2 is the only even prime number
        if (n == 2) {
            return true;
        }
        if (n % 2 == 0) {
            return false;
        }
        // test only odd divisors up to the square root
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] samples = {1, 2, 9, 17, 97};
        for (int value : samples) {
            System.out.println(value + " is prime: " + isPrime(value));
        }
    }
}

출력:

1 is prime: false
2 is prime: true
9 is prime: false
17 is prime: true
97 is prime: true

조건 i * i <= n 이 방법은 Math.sqrt에 대한 부동 소수점 호출을 피하고, 2씩 증가시켜 짝수 약수를 건너뜁니다. 1,000,003과 같은 값의 경우 기본 루프는 약 500,000번의 반복을 수행하는 반면, 이 버전은 500번 미만의 반복을 수행합니다.

사용자가 입력한 소수를 확인합니다

하드코딩된 입력은 데모에는 편리하지만, 실제 문제에서는 대개 키보드 입력이 필요합니다. Scanner 클래스는 콘솔에서 정수를 읽어 isPrime 메서드에 전달합니다.

import java.util.Scanner;

public class PrimeCheckUserInput {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int number = sc.nextInt();

        boolean isPrime = number > 1;
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                isPrime = false;
                break;
            }
        }

        System.out.println(number + (isPrime ? " is a Prime number" : " is not a Prime number"));
        sc.close();
    }
}

샘플 실행:

Enter a number: 29
29 is a Prime number

소수 찾기 프로그램을 작성할 때 흔히 저지르는 실수

대부분의 잘못된 제출물은 메인 루프보다는 경계값에서 오류가 발생합니다. 아래 목록은 초보자 코드에서 가장 자주 나타나는 오류들을 다룹니다.

1. 루프를 1부터 시작합니다: 모든 정수는 1로 나누어 떨어지므로 플래그는 즉시 false로 설정되고 프로그램은 어떤 숫자도 소수가 아니라고 보고합니다.
2. 1을 소수로 취급하는 경우: 값 1은 약수가 하나뿐이므로 약수가 두 개라는 조건을 만족하지 못하므로 false를 반환해야 합니다.
3. break 문을 생략하면 다음과 같습니다. 프로그램은 여전히 ​​정답을 반환하지만, 결과가 나온 후에도 계속 반복 실행되어 입력값이 클 경우 시간이 낭비됩니다.
4. 사용 i <= n 경계선으로서: 이 숫자는 항상 자기 자신을 나누므로, 반복문은 n에 도달하기 전에 멈춰야 합니다.
5. 비교 = 대신 ==: 등호 하나만 사용하면 값을 테스트하는 대신 값을 할당하게 되어 if 조건문에서 컴파일 오류가 발생합니다.

주요 검증 방법 비교

입력값의 크기와 단일 값 또는 전체 범위 테스트 여부에 따라 적절한 방법을 선택하십시오.

단일 값이 아닌 전체 범위를 분류해야 할 때는 체가 훨씬 더 효율적입니다. 저희의 보조 프로그램은 이러한 분류 체계를 찾는 데 도움을 드립니다. 청춘 Numbers 1에서 100에 해당 패턴을 보여줍니다. 관련 루프 기반 연습 문제는 다음을 참조하십시오. 피보나치 수열 Java 밸리 Java 회문 프로그램및 Bubble 정렬 알고리즘 Java깃발 선언과 카운터 입력 방법을 다시 한번 확인하고 싶은 초보자분들은 다음 내용을 읽어보세요. Java 변수 메인에 Java 지도 시간.

자주 묻는 질문