[java] 소수 구하는 아이디어

소수: 1과 자기 자신으로만 나눠지는 수 (2, 3, 5, 7, 11 ...)

 

소수 판별 핵심!! - 2부터 √n까지만 나눠보면 된다.

→ 그 이상의 약수는 이미 쌍으로 발견되기 때문

 

소수 판별 함수 만들기

public static boolean isPrime(int n){
    if(n < 2) return false;
    for(int i = 2 ; i * i <= n; i++){
        if(n % i == 0) return false;
    }
    return true;
}

포인트

• Math.sqrt(n) 대신 i * i <= n 사용
  • Math.sqrt는 매 루프마다 제곱근 계산 (부동소수점 연산)
  • i * i는 단순 곱셈이라 더 빠름
  • 범위가 클수록 차이가 커지므로 습관으로 들이기

 

 

적용한 전체 코드

import java.util.Scanner;

public class Main {
    public static boolean isPrime(int n){
        if(n < 2) return false;
        for(int i = 2 ; i * i <= n; i++){
            if(n % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt();
        int b = sc.nextInt();

        int sum = 0;
        for(int i = a ; i <= b ; i++){
            if(isPrime(i)) sum += i;
        }

        System.out.println(sum);
    }
}