1929번 문제 : 소수구하기

1929번: 소수 구하기 (acmicpc.net)

1929번: 소수 구하기

쉬워보인다.

소수란 ? ) 약수가 1과 자기자신 밖에 없는 수

 

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int m=0;
		int n = 0;
		int count;
		StringTokenizer st = new StringTokenizer(br.readLine());
			m = Integer.parseInt(st.nextToken());
			n = Integer.parseInt(st.nextToken());

		for(int i=m;i<=n;i++) {// m부터 n까지 반복
			count=0; //약수가 1과 자기자신 제외 있는 거 세는 카운트
			for(int j=2;j<i;j++) {
				if(i%j ==0)
					count++;
			}
			if(count ==0) {
				System.out.println(i);
			}
		}
	}
}

정말 간단하게 구현완료.  근데 시간초과가 뜬다.

 

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int m=0;
		int n = 0;
		int count;
		
		StringTokenizer st = new StringTokenizer(br.readLine());
			m = Integer.parseInt(st.nextToken());
			n = Integer.parseInt(st.nextToken());
		int arr[] = new int[n-m+1];
		for(int i=0;i<arr.length;i++) {
			arr[i] = m;
			m++;
		}
		
		for(int i=0;i<arr.length;i++) {// m부터 n까지 반복
			count=0; //1과 자기자신 제외 약수가 있는 거 세는 카운트
			for(int j=2;j<arr[i];j++) {
				if(arr[i] % j ==0)
					count++; //요소를 1과 자기자신이 아닌 다른 수로 나누어 떨어지면 소수가 아님
			}
			if(count ==0) //소수이면
				System.out.println(arr[i]);
		}
	}
}

배열로 바꿔서 m부터 n까지의 수를 저장하고 비교했는데 1%까지 되고 또 시간초과가 났다.

 

출력을 StringBuilder로 바꿔봤는데도 시간초과가 떴다. 뭔가 다른 방법을 써야하나보다.

찾아보니까 1. 제곱근을 이용한 풀이 2. 에라토스테네스의 체 .. ? 라는게 있따 ...

공부를 해야겠다.

 

에라토스테네스의 체 : 2의 제곱, 3의 제곱, 4의 제곱 을 소거하여 남는 수가 소수라는 원리

 

후.. 어렵다...

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int m=0;
		int n = 0;
		
		StringTokenizer st = new StringTokenizer(br.readLine());
			m = Integer.parseInt(st.nextToken());
			n = Integer.parseInt(st.nextToken());
		int arr[] = new int[n+1];
		for(int i=0;i<=n;i++) {
			arr[i] = 0;
		}
		arr[0] = 1; //0과 1은 소수가 아님
		arr[1] = 1;
		
		for(int i=2;i<=Math.sqrt(n);i++) { //2부터 범위 끝의 제곱근(4) 까지 반복 그 수들의 약수를 없애줘야하니까
			if(arr[i] == 1) continue;
			for(int j =i*i; j<=n; j+=i ) {
				arr[j] = 1; //소수가 아닌 수 1로 값 초기화
			}
		}
		for(int i=m;i<=n;i++) {
			if(arr[i] == 0)
				System.out.println(i);
		}
	}
}

내가 이해한 바로는 start부터 end까지의 소수를 구하고 싶다 ! 하면

1. 배열을 end+1만큼을 만든다. - 배열 인덱스 자체를 소수 판별할 수로 씀 

2. 배열은 0부터 시작이니까 arr[0]과 arr[1]에 1이든 true이든 소수가 아닌 수를 판별할 값을 넣는다.

3. 반복문 두개를 돌 건데 겉 반복문은 int i=2~end의 제곱근까지 반복 안 반복문은 i*i부터 end까지 반복, 증감은 j+=i

겉 반복문은 끝 수의 제곱근 보다 작은 제곱근들에서 도는 거고 (1씩 증가하는데 어캐되냐? 하면 조건문을 넣어줘서 이미 값이 판별이 됐다면 다음 반복으로 넘어가게 continue)

안 반복문은 일단 처음 제곱근 2는 당연 소수니까 두고 i*i를 해서 4니까 arr[j]를 소수 아닌 값 넣어줌 j+=i의 의미는 i값의 배수를 다 소수가 아닌 값을 바꿔주기 위함이다.

//arr배열 전체 값을 0으로 초기화 해줘야함

arr[0] = 1; 
arr[1] = 1; //0과 1은 소수가 아님

for(int i=2;i<=Math.sqrt(end);i++){
	if(arr[i] == 1) continue; //1이면 이미 소수가 아닌 값으로 판별난 데이터임-> 다음 반복
    for(int j=i*i;j<=end;j+=i){// i,j 값이 인덱스이면서 판별할 수 그 자체임.
    //그래서 맨 처음 제곱근의 제곱을 해서 그 값을 소수가 아닌 수를 넣고 j+=i는 그 j의 값의 배수를 소수가 아닌 수로 판별해줄려고 한 거임
    	arr[j] = 1; 
    }
}
for(int i=start;i<=end;i++){
	if(arr[i] ==0)
     System.out.println(i);
}

핵심코드.. 

후 어렵네 !

 

그리고 또 새로 써본 거 BufferedWriter

57931129 StringBuilder 썼을 때  이게 젤 빠르네 !

57930954 BufferedWriter 썼을 때

57929806그냥 System.out으로 출력했을 때