에라토스테네스의 체 알고리즘을 알고 있어야 해결할 수 있는 문제였다. 이 알고리즘만 확실하게 알면 어렵지 않게 풀 수 있다. 난 이 알고리즘을 몰랐기 때문에 시간 초과로 틀렸다. 알고리즘에 대한 자세한 설명은 여기 글에 적어놨다. https://byungil.tistory.com/197 에라토스테네스의 체 알고리즘 - 소수 구하기 알고리즘 우리는 에라토스테네스의 체(Sieve of Eratosthenes)라는 방법을 통해 보다 쉽게 소수를 찾아낼 수 있습니다. 이름 그대로 체를 통해 무언가를 걸러내듯이 소수를 찾는 방법입니다. 일반적으로 소수만 byungil.tistory.com = 접근 방법 ( 틀린 이유 ) = 내가 처음 접근한 소수 찾는 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 1..
우리는 에라토스테네스의 체(Sieve of Eratosthenes)라는 방법을 통해 보다 쉽게 소수를 찾아낼 수 있습니다. 이름 그대로 체를 통해 무언가를 걸러내듯이 소수를 찾는 방법입니다. 일반적으로 소수만 구하려면 2중 for문을 이용해 시간 복잡도는 O(N^2)라고 판단할 수 있다. 에라토스테네스의 체 알고리즘을 이용하면 시간 복잡도는 O(Nlog(logN))이다. 배수를 삭제하는 연산으로 바깥 for문을 생략하는 경우가 발생하기 때문이다. 찾을 범위까지 수를 나열한 다음, 소수가 아닌 1을 지웁니다. 1 다음으로 큰 소수인 2를 남겨두고 2의 배수를 모두 지웁니다. 2 다음으로 큰 소수인 3을 남겨두고 3의 배수를 모두 지웁니다. prime(n) 다음으로 큰 소수인 prime(n+1)을 남겨두고 ..
= 내가 접근한 방법 = import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOException { // 1. input BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); StringTokenizer st = new StringTokenizer(br.readLine()); int n = ..
