[백준 1750] 서로소의 개수

https://www.acmicpc.net/problem/1750

1750번: 서로소의 개수

 

https://velog.io/@yerin4847/W1-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법(Euclidean-algorithm)

 

https://nicotina04.tistory.com/47

백준 1750 - 서로소의 개수

 

 

//오답 (TC2 번 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;

public class Main {
    private static int MAX_NUM = 10000003;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < N; i++) {
            set.add(Integer.valueOf(br.readLine()));
        }
        Integer[] seq = set.stream().toArray(Integer[]::new);
        int num = seq.length;
        int remainder = 0;
        for (int i = 0; i < num; i++) {
            for (int j = i + 1; j < num; j++) {
                if (isPrimeNumber(seq[i], seq[j])) {
                    remainder += (Math.pow(2.0, (num - 1.0) - j)) % MAX_NUM;
                    remainder %= MAX_NUM;
                }
            }
        }
        if (remainder != 0) remainder++;
        System.out.println(remainder);
    }

    private static boolean isPrimeNumber(int a, int b) {
        int tmp;
        int dividend = Math.max(a, b);
        int remainder = Math.min(a, b);
        do {
            tmp = dividend % remainder;
            dividend = remainder;
            remainder = tmp;
        } while (remainder != 0);
        if (dividend == 1) {
            return true;
        }
        return false;
    }
}