백준 1978 소수찾기 (JAVA)

소수찾기 복잡도 개선한 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc  = new Scanner(System.in);
        int testCase = sc.nextInt();
        int result = 0;

        for(int i = 0 ; i < testCase ; i++) {
            if(isDecimal(sc.nextInt()))
                result++;
        }
        System.out.print(result);
        sc.close();
    }

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

}

for(int i = 2 ; i*i <= num ; i++) { sqrt(n)만큼만 돌리는 것으로 개선(소수는 짝을 짓게되므로)

이전 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int testCase = sc.nextInt();
        int num;
        int result = 0;

        for(int i = 0; i < testCase; i++) {
            num = sc.nextInt();
            if(isDecimal(num))result++;
        }
        System.out.println(result);
        }

    public static boolean isDecimal(int n) {
        boolean flag = true;

        if(n<2) return false;
        else for(int i = 2; i < n; i ++)
            if(n%i == 0)
                flag = false;
        return flag;
    }

}

else for(int i = 2; i < n; i ++) // 기존의 것은 O(n)이었음