소수 구하기

소수 구하기

Question - 1929

Code

import java.util.Scanner;

public class N37_P1929_소수_구하기 {

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

        int[] A = new int[N + 1];

        for (int i = 2; i <= N; i++) {
            A[i] = i;
        }

        for (int i = 2; i <= Math.sqrt(N); i++) {
            if (A[i] == 0) {
                continue;
            }

            for (int j = i + i; j <= N; j = j + i) { // 배수 지우기
                A[j] = 0;
            }
        }

        for (int i = M; i <= N; i++) {
            if(A[i] != 0) {
                System.out.println(A[(int) i]);
            }
        }
    }
}

Insight

Idea

• 수학

• 정수론

• 소수 판정

• 에라토스테네스의 체

reference

나머지 합 구하기

Question - 1456

Code

import java.util.Scanner;

public class N38_P1456_나머지_합_구하기 {

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

        long min = sc.nextLong();
        long max = sc.nextLong();

        long[] A = new long[10000001];
        for (int i = 2; i < A.length; i++) {
            A[i] = i;
        }

        for (int i = 2; i <= Math.sqrt(A.length); i++) {
            if (A[i] == 0) {
                continue;
            }

            for (int j = i + i; j < A.length; j = j + i) {
                A[j] = 0;
            }
        }

        int count = 0;
        // 거의 소수 구함. 소수의 n제곱
        // 거의 소수 + min, max 문제 조건 
        for (int i = 2; i < 10000001; i++) {
            if (A[i] != 0) {
                long temp = A[i];
                while ((double)A[i] <= (double)max/(double)temp) {
                    if ((double)A[i] >= (double)min/(double)temp) {
                        count++;
                    }
                    temp = temp * A[i];
                }
            }
        }
        System.out.println(count);
    }
}

Idea

reference

소수 & 팰린드롬 수 중에서 최솟값 찾기

Question -1747

Code

import java.util.Scanner;

public class N39_P1747_소수_팰린드롬_수_중_최솟값 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[10000001];
        for (int i = 2; i < A.length; i++) {
            A[i] = i;
        }

        for (int i = 2; i < Math.sqrt(A.length); i++){
            if (A[i] == 0) {
                continue;
            }

            for (int j = i + i; j < A.length; j = j + i) {
                A[j] = 0;
            }
        }

        int i = N;
        while(true) {
            if (A[i] != 0) {
                int result = A[i];
                if (isPalindrome(result)) {
                    System.out.println(result);
                    break;
                }
            }
            i++;
        }
    }

    private static boolean isPalindrome(int target) {
        char temp[] = String.valueOf(target).toCharArray();
        int s = 0;
        int e = temp.length - 1;
        while (s < e) {
            if (temp[s] != temp[e])
                return false;
            s++;
            e--;
        }
        return true;
    }
}

Idea

reference

제곱이 아닌 수 찾기

Question -1016 {

Code

import java.util.Scanner;

public class N40_P1016_제곱이_아닌수_찾기 {

    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        long min = sc.nextLong();
        long max = sc.nextLong();
        boolean[] check = new boolean[(int) (max - min + 1)];

        for (long i = 2; i * i <= max; i++) {
            long pow = i * i;
            long start_index = min / pow;
            if (min % pow != 0)
                start_index++;
            for (long j = start_index; pow * j <= max; j++) {
                check[(int) ((j * pow) - min)] = true;
            }
        }
        int count = 0;
        for (int i = 0; i <= max - min; i++) {
            if (!check[i]) {
                count++;
            }
        }
        System.out.println(count);
    }
}

Insight

Idea

• 수학

• 정수론

• 소수 판정

• 에라토스테네스의 체

reference