[2020여름] 모각코 6회차 활동

백준 1929번

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

1929번: 소수 구하기

1929번

입력 받은 숫자 두 개의 범위 안에 속하는 소수를 출력하는 문제다.

 

처음에는 

소수를 저장하는 LinkedList를 하나 만들어서

for문을 돌려서 LinkedList 안에 있는 모든 원소와 나눴을 때 나머지가 모두 0이 아니면 LinkedList에 추가하는 식으로 코드를 구현하였는데 시간 초과가 떴다!!

 

그래서 어떻게 시간을 줄여야할지 구글링을 하다보니!!!

 

이 문제가 에라토스테네스의 체를 사용하는 문제인 것을 발견했다.

 

문제 해결

에라토스테네스의 체

https://seunghee114-blog.tistory.com/70

[알고리즘] 에라토스테네스의 체

코드

package bj1929;

import java.util.Scanner;

public class Main2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();

		int[] check = new int[y + 1];

		for (int i = 2; i <= y; i++) {
			check[i] = i;
		}

		for (int i = 2; i <= y; i++) {
			if (check[i] == 0) {
				continue;
			}

			for (int j = 2 * i; j <= y; j += i) {
				check[j] = 0;
			}

		}

		for (int i = x; i <= y; i++) {
			if (check[i] != 0) {
				System.out.println(check[i]);
			}
		}

	}

}