1929번 '소수 구하기'

import java.io.*;

import java.util.*;

class Main {

public static void main(String[] args) throws IOException {

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

String[] input = in.readLine().split(" ");

final int m = Integer.parseInt(input[0]);

final int n = Integer.parseInt(input[1]);

int count = 0;

int[] array = new int[n + 1];

boolean[] isCleared = new boolean[n + 1];

for(int i=2; i<=n; ++i) {

isCleared[i] = false;

}

for(int i=2; i<=n; ++i) {

if(!isCleared[i]) {

array[count++] = i;

for(int j = i * 2; j<=n; j+=i) {

isCleared[j] = true;

}

}

}

for(int i: array) {

if(i < m) continue;

if(i == 0) break;

System.out.println(i);

}

}

}

소수에 대한 정리

• 특정 수의 N의 소수 여부 판별을 위해서는 (2...sqrt(N)) 을 돌면서 나누어 떨어지지 않는 것을 확인하면 된다.
• 1부터 N까지의 자연수의 소수 여부 판별을 위해서는 에라토스테네스의 체 알고리즘을 사용한다.
• 소수를 저장할 빈 배열
• 소수의 개수를 저장할 변수
• 소수를 저장할 빈 배열의 인덱스로 활용 가능
• Swift에서는 빈 배열에 append하는 방식으로 진행할 수 있으므로 딱히 필요 없음
• 수가 지워졌는가를 확인하기 위한 false로 꽉 차있는 배열
• 2부터 N까지 순회하면서, 해당 인덱스(수)의 불리언 값이 false이면(지워지지 않았다면) 그 수는 소수이므로 소수 저장 배열에 추가하고 그 배수들을 지워나간다(불리언 값을 true로 설정한다).

let input = readLine()!.split(separator: " ").map { Int($0)! }

let m = input.first!

let n = input.last!

var primes = [Int]()

var isCleared = Array(repeating: false, count: n + 1)

for i in 2...n {

    if !isCleared[i] {

        primes.append(i)

        for j in stride(from: i * 2, through: n, by: i) {

            isCleared[j] = true

        }

    }

}

for prime in primes {

    if prime < m { continue }

    print(prime)

}