# 소수 구하기

### 소수 구하기&#x20;

#### Question - 1929

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FD60JmcLmSmgiH5btwYl9%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-02%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.54.56.png?alt=media\&token=45d82e22-2967-4054-8497-ec0e7c0e2655)

#### Code

```java
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&#x20;

#### Idea&#x20;

* 수학
* 정수론&#x20;
* 소수 판정&#x20;
* 에라토스테네스의 체&#x20;

#### reference



### 나머지 합 구하기&#x20;

#### Question - 1456&#x20;

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2F8De0gEiGpfh146axY3Or%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-02%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.57.08.png?alt=media\&token=1e9706a8-a5a9-4003-9053-d3b663065ee0)

#### Code

```java
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



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

#### Question -1747&#x20;

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FXfFs969BPpM2UIs6dmTL%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-02%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.58.48.png?alt=media\&token=40f876ba-39ee-4f84-9c6a-1736adcb0ccb)

#### Code

```java
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



### 제곱이 아닌 수 찾기&#x20;

#### Question -1016  {



![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2Fmr6o69ZRsjdTNWn5g6Es%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-02%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.59.12.png?alt=media\&token=3cb88638-1aed-441f-9559-c3c3ca736938)

#### Code

```java
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

* 수학
* 정수론
* 소수 판정
* 에라토스테네스의 체&#x20;

#### reference
